Als das Dorf Schwamendingen 1934 in die Stadt Zürich eingemeindet wurde, gehörte dessen katholische Bevölkerung noch zur Pfarrei Oerlikon. Damals hatte Schwamendingen ungefähr 2‘500 Einwohner. Der Anteil an Katholiken war überschaubar, denn deren Konfession war im reformierten Zürich erst seit Anfang des 19. Jahrhunderts toleriert.
Dann explodierte die Bevölkerung. 1950 hatte Schwamendingen schon 14‘000, 1960 sogar über 33‘000 Einwohner. Auch viele Katholiken zogen in die Neubausiedlungen am nordöstlichen Stadtrand von Zürich. Die Pfarrei Oerlikon platzte aus allen Nähten. Deshalb gab sie 1947 für Schwamendingen die Planung einer Notkirche aus Holz in Auftrag, deren Baubewilligung jedoch von der Züricher Stadtbehörde verweigert wurde. Die Neubausiedlungen von Schwamendingen galten damals als städtebaulich mustergültig, und man befürchtete, dass die Ästhetik des aufstrebenden Quartiers durch ein barackenähnliches Kirchenprovisorium gestört werden könnte. Mutig investierten die Katholiken deshalb in die Planung eines architektonisch überzeugenden Gotteshauses und engagierten den bedeutenden Schweizer Architekten Fritz Metzger (1898–1973), der zuvor (1934–1935) unter anderem schon die Sankt Gallus-Kirche von Oberuzwil gebaut hatte. Metzger erstellte 1951 einen schlichten zweigeschossigen Bau, in dem neben einer Kapelle auch ein Pfarrhaus Platz fand. Schwamendingen war im Dezember 1950 von der Mutterkirche Oerlikon getrennt und zur eigenen Pfarrei erhoben worden.
Kaum gebaut, war die Kapelle schon wieder zu klein. Schwamendingen wuchs ungebremst weiter. Bereits am 20. Mai 1956 wurde neben der bestehenden Kapelle der Grundstein für eine neue Kirche gelegt. Diese konnte am 23. Juni 1957 geweiht werden und erhielt Sankt Gallus als Patron. Ihr Patrozinium verdankte die Kirche dem engagierten Prälaten Franz Höfliger (1892–1985), der zwischen 1949 und 1966 als Seelsorger in Schwamendingen tätig war. Höfliger verstand sich wie Gallus als Missionar und war wie dieser ein begnadeter Prediger. Um den Bau der neuen Kirche finanzieren zu können, hielt Höfliger zahlreiche Bettelpredigten, die ihn weit über die katholische Schweiz hinaus bekannt machten.