Nowy Bytom, popularnie po śląsku zwany Fryną, jest dzielnicą Rudy Śląskiej, położoną we wschodniej części miasta. Osada rozwinęła się dopiero w XIX i XX wieku. W 1911 roku w centrum miejscowości wybudowano monumentalny kościół pod wezwaniem św. Pawła. Architekt Johannes Franziskus Klomp stworzył dzieło niepospolite, reprezentujące stylistycznie głównie neoromanizm, ale nie pozbawione elementów wczesnochrześcijańskich czy bizantyńskich.
Nazwa Nowy Bytom pojawiła się na mapach Śląska bardzo późno, bo dopiero w XX wieku. Najwcześniej tereny te znano jako Bytomski Czarny Las, czego pozostałością jest dzisiejsza ulica Czarnoleśna. Pod koniec XVIII wieku zbudowano tutaj pierwszą kopalnię węgla kamiennego, co pociągnęło za sobą rozwój przemysłowy. Wkrótce powstały następne kopalnie oraz huta cynku „Rozamunda”. Przełomowe okazało się uruchomienie w 1840 roku huty „Friedenshütte” („Pokój”), która dała nazwę wyrosłej przy niej osadzie. Miejscowość Nowy Bytom zaistniała dopiero w 1922 roku. Decyzję o nadaniu jej praw miejskich podjął Sejm Śląski w 1939 roku. Po dwudziestu latach z połączenia Nowego Bytomia i Rudy powstało miasto Ruda Śląska.
Pierwszy kościół, pod wezwaniem św. Józefa, w Nowym Bytomiu wzniesiono w latach 80. XIX wieku (w 1931 roku musiał zostać wyburzony z powodu szkód górniczych). Na początku ubiegłego wieku liczba wiernych parafii św. Józefa stale się rozrastała, co stworzyło potrzebę wymurowania nowej świątyni. Zabrał się za to ks. Edward Adamczyk i w 1911 roku położono kamień węgielny pod budowę drugiego kościoła w Nowym Bytomiu. Projektantem świątyni był znany niemiecki architekt pochodzenia holenderskiego - Johannes Franziskus Klomp. Połączył on w gmachu świątyni różne style – dominuje neoromanizm, ale uzupełniony jest on elementami sztuki wczesnochrześcijańskiej, biznatyńskiej, ottońskiej, a nawet orientalnej.
Kościół św. Pawła wzniesiono na planie krzyża łacińskiego; do korpusu nawowego i wieży dostawiono liczne przybudówki. Zastosowano układ bazylikowy z trzema nawami, transeptem i prezbiterium zamkniętym półkolistą absydą. Nad przecięciem nawy głównej z transeptem umieszczono niewielką kopułę. Najsilniejszym akcentem jest masyw wieżowy, urozmaicony licznymi mniejszymi wieżyczkami, które są przykryte kopułami. Właściwa wieża wyrasta znad fasady potężnym prostopadłościanem, który następnie przyjmuje formę ośmiokąta; wieńczy ją kopuła z latarnią. Bardzo bogata jest dekoracja rzeźbiarska kościoła. Przed wejściem głównym umieszczono kamienne postacie św. Floriana (patrona hutników) i św. Barbary (patronki górników). Wnikliwy obserwator odnajdzie na zewnątrz i wewnątrz świątyni inne figury świętych, płaskorzeźby, motywy zwierzęce i roślinne oraz inskrypcje z cytatami z Pisma Świętego i ksiąg Doktorów Kościoła.