Non sono rimaste nemmeno tracce della chiesa del IV secolo dedicata ai Santi Apostoli, che fu sostituita nel 536 dalla chiesa giustinianea e nel 1469 dalla moschea di Maometto il Conquistatore, la Fàtih.
La prima novità che osserviamo è la pianta a croce greca (ovvero con tutti i bracci uguali), cui era annesso un mausoleo (che era la tomba di Costantino); le cinque cupole che vediamo al di sopra della copertura sono un’intervento di Giustiniano, perché per un incendio viene distrutta e completamente ricostruita nel VI secolo. Ora per capire meglio come era fatta la chiesa dei Santi Apostoli dobbiamo rivolgersi alle fonti storiche, le quali dicono che Giustiniano ha costruito ad Efeso la chiesa di san Giovanni, su modello della chiesa dei Santi Apostoli (aggiungendo un’altra campata).
L'edificio giustinianeo riprese da quello costantiniano la pianta cruciforme, col braccio d'ingresso forse leggermente più lungo degli altri tre. Cinque cupole erano sostenute da massicci pilastri agli angoli della croce e coprivano sia i bracci che la crociera; navatelle e gallerie correvano su quattro lati dei singoli bracci e si aprivano sulle navate attraverso due file di colonne. Sotto la cupola centrale, l'unica che fosse illuminata da finestre, era situato il presbiterio cruciforme; le altre cupole erano buie e chiaramente un po' più basse, forse erano semplici cupole a vela.