Pausanias addresses the two building complexes at the Western edge of the Sanctuary of Zeus in Olympia as “Palaestra” and “Gymnasium”. This suggests the imagination these buildings were connected with the polis institution of the gymnasium. As Olympia is far away from every ancient city this concept is not convincing. Otherwise extra urban sanctuaries on the Peloponnesus contain a range of facilities for athletes like buildings for washing and preparation for sport activities. These buildings are related to palaestrae where rooms with similar functions and furnishment represent the most distinctive features of the building type. Strikingly, the palaestra and these facilities emerged during the 2nd half of the 4th century BC. An investigation of extraordinary features in “gymnasial buildings” in different contexts sheds new light on the emergence of the palaestra. It seems that the development of gymnasial architecture was not only tracing back to (literary known) Athenian archetypes but also to experimentation with specific functional buildings in 4th century Greece. It seems that the quotation of palaestra buildings in Olympia emphasizes the joint roots of architecture of athletics in sanctuaries and gymnasia.