W latach 1873-1875 pojawiły się pierwsze plany postawienia nowego kościoła. Nie udało się zrealizować ich ks. Edwardowi Bolikowi - zmarł w 1899 roku - ale doprowadził je do końca jego następca ks. dr Franciszek Brudniok. Pozwolenie na budowę kościoła w Rybniku z wrocławskiej kurii nadeszło wiosną 1903 roku. Same prace budowlane zaś ruszyły 14 września tegoż roku. Projekt architektoniczny kościoła opracował Ludwik Schneider.
Do końca 1903 roku zabetonowano fundamenty kościoła. Kolejne prace rozpoczęto od wiosny 1904 roku, wieńcząc je wzniesieniem murów. Udział w tym miało 138 osób. 1905 rok wykorzystano na ułożenie poszycia dachowego oraz wymurowanie wież. W rok później uporządkowano obejście kościoła, zawieszono dzwony i wyposażono wnętrze. W listopadzie 1906 roku rozebrano też znajdującą się w pobliżu kaplicę św. Antoniego. Koszt budowy kościoła początkowo szacowano na 346 tys. marek. W rzeczywistości przekroczył on sumę 560 tys. marek.
Na planie krzyża łacińskiego powstał kościół trójnawowy, z transeptem i rozbudowaną częścią prezbiteralną, posiadający wszystkie cechy stylu gotyckiego. Jego wieże wzniosły się na wysokość 95 m; stąd to najwyższy obiekt sakralny na Górnym Śląsku często nazywany "katedrą ziemi rybnickiej". Wewnątrz umieszczono 14-metrowy, neogotycki ołtarz główny wykonany w latach 1906-1907 w warsztacie Carla Buhla.
29 września 1907 kościół został poświęcony, a 30 września 1915 jego konsekracji dokonał bp Adolf Bertram. 22 czerwca 1921 kościół poważnie ucierpiał w wyniku eksplozji materiałów wybuchowych na bocznicy rybnickiego dworca. Ponownie kościół uległ zniszczeniu podczas działań frontowych w 1945 roku.
27 sierpnia 1950, na prośbę kurii, wiernym przekazano informację o utworzeniu samodzielnej stacji duszpasterskiej przy kościele św. Antoniego z Padwy w Rybniku. Sam zaś dekret erekcyjny kuracji wszedł w życie 10 lutego 1952. W listopadzie 1991 roku rybnicki kościół stał się zabytkiem sztuki klasy "A". W czerwcu 1993 roku został podniesiony do godności bazyliki mniejszej. W 2005 roku przy wejściu do kościoła odsłonięto pomnik Jana Pawła II. W dwa lata później - z okazji 100-lecia poświęcenia kościoła - na wieży zawisł ponad 3,5 tonowy Dzwon Miłosierdzia Bożego odlany w ludwisarni Grassmayerów w Innsbrucku.