The Baptistery of Saint Paul is located at the entrance of the village Agios Ioannis (Saint John), near Phaestus. According to tradition, when the Apostle Paul came to Crete and headed to the capital of the island, Gortyn, passed from the point where he taught Christianity for two days. In this place was built (unknown when) the Baptistery, which was originally a square building with a low dome.
In 1304 a square room with a dome was added to the baptistery and the original part was turned into the sanctuary of the church of Saint Paul (Agios Pavlos). The church was adorned with frescoes; some fragmentary iconographic decoration of the 14th century survives that includes scenes of Saint John the Baptist (an event expected in a baptistery), the Pantocrator and the Second Coming in the dome, the Evangelists in the spherical triangles, a few evangelical scenes and saints.
An important inscription is preserved in the dome of the church, which states that the "temple of Saint Paul was restored and frescoed, at the position of the baptistery, with the help of the Byzantine Emperor Andronikos Palaeologos, lady Irene and his son Michael. Year 6812 from the conquest of the world (1308)".