Før Sundbyerne fik egne kirker, måtte sognebørnene gå hele vejen ud til kirken i Tårnby. 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.
Sundby Kirke blev opført 1869-1870 efter tegninger af arkitekt Hans Jørgen Holm. Grunden hvor kirken ligger, blev skænket af firmaet Jacob Holm & Sønner.
To år efter fik kirken sin egen kirkegård, der ikke ligger ved kirken, men mellem >Kirkegårdsvej og Backersvej.
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. På det tidspunkt var der 12.000 indbyggere i sognet.
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.
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.
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.
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.