Bardzo trudno określić dokładną datę powstania parafii św Marii Magdaleny. Szacuje się, że pierwsza drewniana kaplica powstała w latach 1138-1166 za czasów księcia sandomierskiego Henryka.
Pierwsze pisemne potwierdzenie istnienia parafii pochodzi z 1326 roku i jest to wykaz dziesięciny papieskiej przesłanej do Rzymu przez parafie biskupstwa krakowskiego. Fakt utworzenia w XVII wieku dekanatu miechocińskiego wskazuje, że według tradycji i zwyczajów Kościoła, parafia miechocińska powstała przed rokiem, 1215 w którym to utworzono parafię gawłuszowicką.
Budowa kościoła miechocińskiego odbywała się w różnych okresach dziejowych co spowodowało, że obecny wygląd kościoła łączy w sobie kilka styli architektonicznych.
Najstarszą częścią kościoła, a zarazem najdawniejszym zabytkiem budownictwa puszczy sandomierskiej jest gotyckie prezbiterium. Zbudowane jest ono z cegły palonej i stanowi prostokąt o wymiarach 8,10 na 5,90 m. Prezbiterium posiada dwa okna gotyckie od strony południowej oraz gotyckie sklepienie.
Po drugiej stronie znajduje się dobudowana później zakrystia, a nad nią skarbiec. Skarbiec posiada dwa przeciwległe, małe okna zabezpieczone kratami. Ściany zewnętrzne są otynkowane i pomalowane na biało.
Z niewielkiej zakrystii do prezbiterium prowadzi niskie przejście z ciężkimi
-pochodzącymi z XIV wieku- kutymi, żelaznymi drzwiami.
Po roku, 1593 kiedy to powstało miasto Tarnobrzeg podjęto decyzję o rozbudowie kościoła. W 1613 roku rozpoczęto trwające kilka lat prace nad pierwszą rozbudową: usunięto część ściany frontowej i dobudowano część nawy głównej, boczne wejście, oraz kaplicę „Babiniec”.
W latach 1843-1845 odremontowano prezbiterium i pierwszą część nawy głównej oraz dobudowano drugą dziesięciometrową część. Długość nawy głównej wraz z przedsionkiem pod chórem wynosi 21,80 m. Dobudowana w tym czasie część nawy ma cztery okna, po dwa z każdej strony. Nad całą nawą główną rozciągał się drewniany sufit.
Ściana czołowa kościoła jest gładka. Górna część ma kształt trójkąta z trzema wgłębionymi krzyżami.
W środkowej części gzymsu jest wmurowana kamienna płyta z datą 1843.
W dolnej część ściany frontowej wmurowane są trzy cegły. Jedna z datą A.D.-1613, druga z napisem „eb.Pru”. Cegły te zostały przeniesione z pierwotnej ściany czołowej. Na trzeciej cegle widnieje data rozbudowy kościoła A.D. 1843
W 1932 roku przystąpiono do renowacji kościoła ze zniszczeń, które powstały w czasie działań wojennych w 1915 r. Naprawiono zewnętrzne ściany uszkodzone pociskami artyleryjskimi, których czerepy wmurowano w miejscach większych uszkodzeń. Pociski te nadal tkwią w murach ukazując kierunek, z jakiego były wystrzelone.
Wzmocniono skarpy przy zewnętrznych ścianach nawy głównej. W następnej kolejności przystąpiono do budowy sklepienia i dachu. Sklepienie w nawie głównej zostało zbudowane w stylu romańskim, a nie tak jak w prezbiterium w stylu gotyckim. Okna w nawie głównej nie są usytuowane symetrycznie między łukami sklepienia tylko pozostawiono je tak jak zostały rozmieszczone pierwotnie.
Podczas wznoszenia sklepienia dokonano przebudowy dachu oraz małej sygnaturki zastępując ją 15 m wysoką wieżyczką zakończoną krzyżem. Wieżyczka i dach pokryte zostały blachą ocynkowaną.
Na miejscu dawnego „babińca” zbudowano okrągłą kaplicę o średnicy 5 m. Kaplica ma murowane kopulaste sklepienie wysokie na 3,5 m . Dach kapliczki tak jak reszta kościoła kryty jest blachą ocynkowaną. Na kopulastym dachu umieszczono latarnię 2,15 m a na niej krzyż z 3 m kopułką.
W 1975 roku na ścianie zewnętrznej wmurowano tablicę upamiętniającą postać Wojciecha Wiącka.
W 1991 roku tablicę poświęconą żołnierzom AK z terenu parafii, którzy oddali życie za Ojczyznę.
W 1993 roku pojawiła się tablica upamiętniająca wieś Machów, którą zajęła kopalnia siarki.
W 1994 roku tablica pamiątkowa wsi Kajmów.
W latach 1987-1988 dokonano wymiany konstrukcji dachu i przykryto kościół blachą miedzianą. W roku 1993 dokonano również częściowej konserwacji prezbiterium oraz ołtarza głównego.