Szybki wzrost liczby ludności spowodowany rozwojem przemysłowym sprawił, że mieszkańcy rozważali powstanie własnego kościoła. Pomysł budowy przedstawiono 8 października 1868 r. na zebraniu gminnym, podczas którego utworzono fundusz na ten cel. Czynnikiem, który przyspieszał budowę kościoła w Dębie, był fakt rosnącej popularności w tym okresie w Katowicach starokatolicyzmu ks. Kamińskiego. Mieszkańcy na patronów wybrali świętego Jana i Pawła Męczenników na pamiątkę tego, jak dnia 26 czerwca w święto Męczenników Dąb został spustoszony przez klęskę żywiołową. Posługę w kościele do 1895 r. pełnili duszpasterze z parafii chorzowskiej.
Powstanie Józefowca, Bederowca i kolonii Agnieszka, osad robotniczych podlegających administracyjnie do Dębu spowodowało, że liczba ludności zwiększyła się do 6 tys. mieszkańców. 18 sierpnia 1894 r. biskup wrocławski kardynał Georg Kopp wydał dekret ustanawiający parafię w Dębie. Pierwszym proboszczem został 8 lipca 1895 r. ks. Maksymilian Krocker. W 1899 r. przybył pierwszy wikary ks. Brunon Zachlod. Kościół został poświęcony dwukrotnie: w 1902 r. przez ks. Wiktora Schmidta oraz w 15 października tegoż roku przez kardynała Koppa.