Wieś Matysówka od niepamiętnych czasów należała do parafii św. Rocha w Słocinie. W 1980 roku Matysówka została przyłączona do parafii Rzeszów – Zalesie, której proboszcz ks. Władysław Janowski został zobowiązany do wybudowania świątyni. W dniu 2 maja 1981 r. Ks. Infułat Jan Stączek, przy współudziale Ks. Dziekana Stanisława Macai Ks. Władysława Janowskiego
, oraz licznie zebranych wiernych, dokonał poświęcenia zrębów świątyni w Matysówce i odprawił pierwszą Mszę św. W lipcu 1982 r. Ks. Biskup Ignacy Tokarczuk mianował proboszczem nowej parafii Ks. Mieczysława Wolanina. Nadal trwały prace wykończeniowe wewnątrz świątyni jak i porządkowanie obejścia kościoła. W marcu 1983 roku został oddany do użytku cmentarz parafialny, a we wrześniu tegoż roku rozpoczęto budowę plebani, która została zakończona wiosną 1984 roku.
Dnia 30 czerwca 1985 roku nastąpiło przejęcie parafii przez nowego proboszcza Ks. Jana
Pyziaka. Wiosną 1988 roku rozpoczęto budowę dzwonnicy, a w roku następnym otynkowano zewnętrzne ściany świątyni i ogrodzono plac kościelny. 26 kwietnia 1991 roku rozpoczęły się pierwsze w historii parafii misje święte, przeprowadzone przez Ks. Franciszka Rząsę i Ks. Stanisława Mazura w10-lecie budowy świątyni. 11 i 12 listopada 1992 r. odbyła się wizytacja parafii przez Ks. Biskupa Kazimierza Górnego, biskupa nowo powstałej diecezji rzeszowskiej. Przy tej okazji Ks. Biskup poświęcił kaplicę cmentarną, oraz grotę Matki Bożej wybudowaną w sąsiedztwie kościoła jako wotum dziękczynne za pielgrzymkę Jana Pawła II do Rzeszowa. W Roku Jubileuszowym 2000 została ufundowana i poświęcona figura św. Józefa, która stoi obok kościoła, a parafię
, w dniach 28-29 lutego nawiedził obraz „Jezu, ufam Tobie”. Rok później rodzina pana Jana Wasilewskiego ufundowała dwa nowe dzwony: „Św. Jan Chrzciciel i Jan Paweł II” oraz „Św. Józef”. W dniach 13-14 VIII 2002 r. parafię nawiedziła kopia obrazu Matki Bożej Częstochowskiej. 3 maja 2006 roku parafia przeżywała uroczysty odpust z okazji 25-lecia budowy świątyni z udziałem Ks. Infułata Stanisława Maca, oraz pierwszego proboszcza Ks. Mieczysława Wolanina. Przez cały czas trwały prace upiększające wnętrze świątyni, jak również jej otoczenie. W 2010 roku pojawił się w kościele nowy ołtarz, ambonka i chrzcielnica.
11 czerwca 2011 roku parafia cieszyła się święceniami kapłańskimi, a następnego dnia prymicjami pierwszego rodaka-kapłana Ks. Kamila Sowy. Z okazji 30 rocznicy męczeńskiej śmierci Ks. Jerzego Popiełuszki i 100-lecia Rycerstwa Niepokalanej pojawiły się obok kościoła figury bł. Jerzego Popiełuszki i św. Maksymiliana Kolbego.
Równolegle z troską o zewnętrzny wygląd świątyni i jej otoczenie, która świadczy o ofiarności i miłości do Bog
a tutejszych parafian, trwa o wiele trudniejsza praca o duchowe oblicze parafii Matysówka, której patronuje Matka Boża Królowa Polski.
20 czerwca 2018 roku parafia przeżywała uroczystość Intronizacji Najświętszego Serca Pana Jezusa, Króla królów i Pana panów wcześniej poprzedzoną peregrynacją tegoż obrazu do rodzin parafii. Natomiast pobożność maryjna parafian pogłębiana jest corocznie pielgrzymką do sanktuarium Pani Łaskawej w Chmielniku i pielgrzymkami do sanktuariów maryjnych w całej Polsce.
25 sierpnia 2018 roku nastąpiła zmiana proboszcza. Dotychczasowy, Ks. Jan Pyziak po 33 latach gorliwej pracy duszpasterskiej w parafii Matki Bożej Królowej Polski w Matysówce przeszedł na emeryturę a nowym proboszczem został Ks. Piotr Fortuna.