Konsekrowany 15 września 1912 roku. Projektantem był Jan Franciszek Klomp (1865–1946), a budowa trwała rok. Budowla architektonicznie łączy w sobie styl romański i bizantyjski. Kościół (nieorientowany) jest budowlą bazylikową, trójnawową z transeptem i prezbiterium, od zachodu zamknięty apsydą z obejściem, od wschodu z wieżą na planie kwadratu. Elewacja kościoła jest bogato zdobiona. Po bokach transeptu widnieją reliefy z postaciami świętych: Augustyna, Hieronima i Ambrożego – po stronie południowej, oraz świętych: Alfonsa bp, Tomasza z Akwinu i Jana Bożego – od strony północnej. Front kościoła ozdobiono reliefami świętych: Pawła, Łukasza i Barnaby. W otwartej kruchcie wejścia głównego środkowa arkada posadowiona jest na kolumnach o cokołach w kształcie lwów. Bryła świątyni charakteryzuje się następującymi wymiarami: długość nawy – 68 m, szerokość – 27 m, wysokość – 18 m, wysokość wieży bez krzyża – 54 m. Dekorację figuralną wykonał artysta z Bytomia Maciej Beule.
Po obu stronach głównego wejścia do kościoła pw. św. Pawła Apostoła w Nowym Bytomiu (plac Jana Pawła II 5) stoją dwie figury lwów, które podtrzymują na swoich grzbietach kolumny portalu. Mieszkańcy dzielnicy darzą je szacunkiem i opowiadają legendę, według której lwy mogą zaryczeć. Może się to zdarzyć podczas ceremonii ślubnej pary, która nie dochowała czystości. Wielu mieszkańców uważa, że owe lwy mają szczególną moc, dlatego traktują je z pietyzmem, a niektórzy sądzą, że poprzez ich dotknięcie, można przejąć od nich energię.