Dokładna data erygowania parafii we Wrzawach nie była znana do lat 50. XX wieku. Dopiero mjr. Józef Rawski, tarnobrzeski regionalista natknął się na nią w aktach wizytacji dekanatu miechocińskiego z 1793 r. Wcześniejsze przekazy podawały informacje, że została ona utworzona przed rokiem 1325. Znalazła się wtedy w wykazie parafii diecezji krakowskiej odprowadzających świętopietrze. Wizytator zapisując najważniejsze informacje o parafiach z dekanatu zanotował, że parafia we Wrzawach została erygowana w 1271 r. Hipotezę taką potwierdzają także wezwania świątyni św. Wawrzyńca, św. Stanisława Biskupa i Męczennika, św. Katarzyny Aleksandryjskiej, które mają charakter typowy dla wspomnianego wieku. Poza tym miejscowość została wymieniona w dokumencie starosty krakowskiego i sandomierskiego Thassa z Vissinburga z 1294 r. Nazywano ją wówczas „Wreuici”. Od 1468 r. funkcjonuje obecna nazwa Wrzawy, co oznacza miejsce, gdzie woda wrze, kotłuje się, tworząc wiry i odmęty. Parafia została wydzielona z terenu parafii Gorzyce jako fundacja rodu Dębno. Opiekę nad nią sprawowały rody szlacheckie: Górajskich, Sienieńskich, Koniecpolskich, Słupeckich, Hadziewiczów i Horochów. Utrzymanie kościoła nastręczało wiele problemów na przestrzeni wieków. Biskup Krakowski Jakub Zadzik wizytując parafię w 1637 r., napisał w dokumentach powizytacyjnych, że w świątyni widać ślady zatopień wodnych, które sięgały nawet do ołtarza głównego. Renowacje kościoła przeprowadzono w połowie XVII wieku. Nową świątynię postawiono wtedy na fundamentach starej. Miała ona prawdopodobnie kształt krzyża, była zbudowana z drewna i nakryta gontem. Według historyków przed kolejnymi powodziami zabezpieczono ją od dołu kłodami. Niestety położenie miejscowości w widłach Wisły i Sanu powodowały dalsze powodzie, które nie omijały wrzawskiego kościoła. Już w XVIII wieku pisano, że podgniłe belki i spojenia zagrażają bezpieczeństwu wiernych. Kolejne powodzie, które nawiedzały Wrzawy latem w latach 1867, 1884 r. oraz zimą 1888 r. powodowały dalsze niszczenie świątyni. Powódź w latach 20. XIX wieku niemalże doprowadziła do całkowitego zniszczenia budowli. Dobroczyńcy wraz z parafianami postanowili wówczas podnieść teren placu kościelnego, co uchroniłoby kolejną świątynię przed dalszymi podtopieniami. Po zakończeniu tych prac, w latach 1826-27 wybudowano nowy kościół. Był to obiekt jednonawowy, wykonany z drzewa modrzewiowego i pokryty gontem. Swoim wyglądem przypominał istniejącą do dnia dzisiejszego drewnianą świątynię w Radomyślu nad Sanem. W latach 20. XIX wieku kościół parafialny został po raz kolejny zalany, co doprowadziło go niemalże do ruiny. Ostatnia drewniana świątynia zbudowana w latach 1826-27 została spalona 4 sierpnia 1944 r. przez wycofujące się wojska niemieckie. Nową murowaną świątynię Najświętszej Maryi Panny Królowej Polski wzniesiono w latach 1958-61 z inicjatywy ówczesnego proboszcza ks. Alojzego Sierżęgi. Projekt kościoła opracował inż. Andrzej Galar z Rzeszowa. Miała to być budowla prosta, ale o stylowej architekturze modernistycznej, posiadająca stromy dach ze strzelistą sygnaturką, wraz ze swoistymi „przyporami” ścian, co miało być nawiązaniem do gotyku. Uroczyste poświęcenie kościoła odbyło się 26 sierpnia 1961 r.