The structure is a stone wall that blocked two-thirds of the entrance to the Theopetra cave near Kalambaka on the north edge of the Thessalian plain. It was constructed 23,000 years ago, probably as a barrier to cold winds.
“An optical dating test, known as Optically Stimulated Luminescence, was applied on quartz grains nested within the stones. We dated four different samples from the sediment and soil materials, and all provided identical dates,” Nikolaos Zacharias, director of the laboratory of archaeometry at the University of Peloponnese, told Discovery News.
This is definitely cool, as there are not very many such structures known from the Paleolithic. One possible, though somewhat shaky, comparable example is that of "two low, roughly linear wall-like piles of cobbles, each about 50m long [that] border a portion of the scatter" of the scatter of mostly Upper Paleolithic stone tools recovered at site MAC064, Iran (Rosenberg 1984:83).
I was surprised, though, that the report refers to the Theopetra structure as the oldest 'man-made' (sic) structure. This is because I can think of at least one other stone structure, at Ucagizli Cave in Turkey (Kuhn et al 2003: 114-116 - available as a free pdf here), that dates to slightly older than ca. 30,000 BP. Here's what it looks like:
And though it appears at first glance to be perhaps less impressive than the Theopetra wall (though the picture in the DN report is a bit unclear as to what the exact boundaries of the wall are), Kuhn et al. (2003: 114) describe the Ucagizli wall as a feature consisting "of a single arched course of limestone blocks, each 20-40cm in length. The blocks form a 'wall' running roughly parallel to the back wall of the cave at a distance of 1.5 to 2m from it. The alignment is clearly artifical: it corresponds with neither the cave's dripline nor any obvious fault or crack in the roof , and there were no blocks of comparable size in the surrounding sediments. Moreover, several of the blocks were set on edge rather than resting on their broad face." By analogy to ethnographic observations, they interpret it as most likely demarcating the edges of "a bedding area in the back of the cave."
So yes, the Theopetra wall is old, but not necessarily the oldest evidence of an artificial stone structure that we have for the Upper Paleolithic. In any case, it'll be very interesting to see what other material is associated with this wall at Theopetra, to see whether or not its interpretation as a windbreak is borne out. As I've discussed before with the case of La Folie, the correlation between features and other aspects of the archaeological record is critical in inferring their ultimate function.
Kuhn, S. L., Stiner, M. C., Kerry, K. W., and Güleç, E. 2003. The early Upper Paleolithic at Üçağızlı Cave (Hatay, Turkey): preliminary results. In Goring-Morris, N., and Belfer-Cohen, A. (eds.) More Than Meets the Eye: Studies on Upper Palaeolithic Diversity in the Near East, Oxbow Books, Oxford, pp. 106-117.
Rosenberg, Michael (1990). Stone "Walls" and Paleolithic Tools: The MAC064 Site Iran, 28, 83-88