Na de Tweede Wereldoorlog groeide de Griekse gemeenschap in Rotterdam sterk, mede door de bloeiende Nederlandse economie en de komst van Griekse scheepvaartbedrijven. De Vereniging der Grieken in Nederland startte kort na de oorlog een inzamelingsactie om een eigen Grieks-Orthodoxe kerk te bouwen. Rotterdam werd gekozen als locatie vanwege zowel de lokale Griekse gemeenschap als de frequente aankomst van Griekse schepen.
In 1950 besloot de Rotterdamse gemeenteraad gratis grond ter beschikking te stellen: een perceel van 346.896 vierkante meter op een uitstekende locatie, achter het Boijmans Van Beuningen Museum. De Griekse architect Antoniades leverde de oorspronkelijke ideeën in Byzantijnse stijl, waarna de Nederlandse architecten De Jongh, Taen en Nix het definitieve ontwerp maakten. Thomas Nix (1904–1998) was hierbij in het bijzonder betrokken.
Op donderdag 4 februari 1954 plantte de toenmalige premier van Griekenland, maarschalk Alexandre Papagos, een eenvoudig houten kruis op de bouwplaats met de inscriptie: ‘Hier wordt een Grieks-Orthodoxe kerk gebouwd.’ Op 27 januari 1955 werd de eerste fundering gelegd, de eerste Grieks-Orthodoxe kerk in Nederland.
De bouw werd begin 1957 voltooid, tegen een totale kostprijs van 144.500 gulden, plus 10.619 gulden voor aanvullende werkzaamheden. Op zaterdag 29 juni 1957, het feest van de heilige Petrus en Paulus, vond de grote inwijding van de kerk plaats.