The emergence of the palaestra as a distinctive building in the form of the peristyle is commonly assigned to the last third of the 4th century BC. While sources show that palaestras existed already earlier, no example has yet been safely identified. This paper argues that some buildings in extra-urban sanctuaries on the Peloponnesus with a set of functions in the context of athletics and competition could represent such early gymnasial buildings. The examples from Nemea and Epidauros lead to the building complex of the Echo Stoa in Olympia which was very likely built as the first palaestra of the precinct. This building complex might reflect the appearance of early gymnasial buildings before the peristyle was introduced as an obligatory architectural form of palaestras.