Ss. Peter and Paul was originally a single nave church with a timber roof and a slightly projecting transverse nave in front of the sacristy. This was an oblong building covered by two low groin vaults and flanked by two rectangular chapels or pastophoria. Rather than forming a semi-circular sanctuary, the east end was square and decorated with a large tripartite opening covering one side.

By the 15^th century four chapels had been added to the south side of the church, one of which still contains the only example of 15^th century wall painting found in Heraklion. Burials have been found in all four chapels, one of which was in a marble relief tomb. The southwest chapel was added in the 14^th century, and was so big that it had an entrance on the south side of the original chapel.