Før Sundbyerne fik egne kirker, måtte sognebørnene gå hele vejen ud til Tårnby Kirke. Nogle søgte derfor kirker i København, måske alene af den grund, at vejen ud til Tårnby om vinteren kunne være lukket.
Derfor ønskede mange sig en kirke i Sundbyerne, og behovet voksede i takt med, at der flyttede arbejderfamilier herud.
Grunden hvor kirken ligger, blev skænket af firmaet Jacob Holm & Sønner.
Sundby Kirke blev opført 1869-1870 efter tegninger af arkitekt Hans Jørgen Holm. Han tegnede kirken som en korskirke i historicistisk stil.
Våbenhuset kom til i 1941.
Over indgangsdøren blev der indsat et relief med titlen “Bøn og arbejde”, der blev udført af billedhuggeren Max Andersen (1892-1972).
Inde i kirken er der glasmalerier, udført af C.N. Overgaard (1851-1929).
Kirken var i de første år en filialkirke af Tårnby Kirke og hed Sundby Kapel, men i 1878 blev sognet udskilt som selvstændigt.
Befolkningstallet i Sundbyerne voksede eksplosivt i 1800-tallets sidste tiår, og derfor byggede man allerede i 1899 endnu en kirke, nemlig Nathanaels Kirke og i 1907 udskiltes Fillips Kirke. I 1935 blev Højdevangskirken bygget i den vestlige del af sognet.
At der var mange børn i sognet, fortæller også erindringer fra kirkens første tid. Pastor Scheekloth beretter, at der ofte var seks brudepar foran alteret på én gang, og én gang blev der døbt 28 børn samme dag. Og præsten oplevede at have otte børnekister foran sig samtidigt.
Sundby Kirke havde i starten mange aktiviteter udover det rent kirkelige. Der var f.eks. en sygeplejeforening, et menighedssamfund, en hedningemissionskreds, KFUM og KFUK samt en søndagsskole, hvor der gik 600 børn. Ungdomsorganisationerne fik til huse i en bygning på Oliebladsgade.
Til kirken hører et menighedshus (billedet herunder), der er tegnet af arkitekt Søren Lemche (1864-1955) og opført 1901-1902.
Fra 1908 havde Sundbyernes Folkebibliotek lokaler i menighedshuset.
To år efter at kirken var åbnet i 1870, blev der anlagt en kirkegård. Den ligger ikke ved kirken, men mellem Kirkegårdsvej og Backersvej.