Historia Legenda thumb|240px|Plan budynku Według późniejszej legendy, za panowania cesarza Justyna I, jego siostrzeniec Justynian został oskarżony o spiskowanie przeciwko cesarzowi, a następnie skazany na śmierć. Jednakże we śnie ukazali się cesarzowi dwaj święci: św. Sergiusz i św. Bakchus, zapewniając go o niewinności Justyniana. W rezultacie przyszły cesarz został uwolniony i przywrócony do godności cezara. Z wdzięczności Justynian ślubował, że gdy zostanie cesarzem poświęci tym dwóm świętym kościół.
Budowa thumb|240px|left|Justynian I Wielki – fundator kościoła. Mozaika z kościoła San Vitale w Rawennie. Budowa kościoła rozpoczęła się w roku 527 i trwała do roku 536. Decyzja o jego powstaniu była jedną z pierwszych jakie podjął Justynian IFreely, Blue Guide Istanbul, pp. 137. Świątynia ta powstała niewiele wcześniej od słynnego kościoła Mądrości Bożej, który wzniesiono między rokiem 532, a 537. Była ona położona na granicy pierwszej i trzeciej dzielnicy (łac. regio) KonstantynopolaMüller-Wiener, 177. Kościół wybudowano pomiędzy tzw. pałacem Hormizdasa (mieszkał tam Justynian zanim wstąpił na tron), a kościołem świętych: Piotra i Pawła. W owym czasie oba kościoły dzieliły wspólny narteks, atrium i propyleje.