Good question. This is such a source of debate that it has been given its own name, "The Homeland Question," and that homeland has its own name, the "Urheimat." Areas from Scandinavia to Siberia have been suggested. These days, the argument has settled down into three areas (at least until the next theory comes along). The first, and most popular, is the area around the northern tip of the Caspian sea. This was suggested by the late Marija Gimbutas, and is known as the "kurgan theory," after the burial mounds or kurgans that are found in that area. The second was proposed by Gamkrelidze and Ivanov in their massive work Indo-European and the Indo-Europeans. This puts the PIEs somewhat further south, in the Caucasus mountains. Since this theory is relatively recent, it has not been properly evaluated, so no one knows how likely it is to be right. The third theory is that of Colin Renfrew, which places the Urheimat in Anatolia. This is the Asian portion of Turkey. He also postulates that Indo-European culture spread by waves of enculturation, with the spread of agriculture, rather than by waves of migration, with the spread of people. His theory has not fared well in the academic world. To note just one problem, it requires Indo-European culture to reach from Anatolia to Greece not by crossing the Bosphorus, but by going east, north over the Black Sea, west, and then down into the peninsula. Not a very sensible way for something to travel, whether people or culture.
So where did the Proto-Indo-Europeans live? Good question, and not one that will be answered in the near future. I myself lean towards the kurgan theory, but if forced to commit myself I will say with Wendy Doniger O'Flaherty that the PIEs came from "east of the asterisk."