W kazaniu abp Adam Szal stwierdził, że odczytana Ewangelia, w której Pan Jezus porównuje królestwo Boże do ziarnka gorczycy bardzo dobrze pasuje do historii tego kościoła i parafii. – Niemal 40 lat temu w 1979 roku w czasie Wielkiego Tygodnia zostało zasiane małe ziarenko. Właściwie minimalne ziarenko, patrząc z perspektywy tej świątyni, w której się znajdujemy. Małe ziarenko, czyli stodoła, w której wystawiono Najświętszy Sakrament zaczęło gromadzić ludzi, aby się modlić. To jest to ziarenko, które przez 40 lat rosło i rośnie dalej – mówił.

Zaznaczył, że siła Kościoła, wiary i każdej parafii leży w tym, „abyśmy patrząc na Chrystusowy krzyż i na zmartwychwstanie, uzmysłowili sobie, że źródłem naszej mocy jest nikt inny, jak tylko Chrystus, Jego męka, śmierć i zmartwychwstanie”. – Wszyscy jesteśmy zaproszeni do tego, aby wejść do Kościoła, do wspólnoty. I aby żyjąc w tej wspólnocie, przyciągać innych, by poprzez życie tej wspólnoty, budziła się w nas i ożywiała duchowa wspólnota prowadząca do świętości – powiedział.

Parafia Matki Bożej Królowej Polski w Przemyślu powstała w 1980 r. Zanim to nastąpiło, przystąpiono do budowy kościoła. W Niedzielę Palmową 8 kwietnia 1979 roku bp pomocniczy Tadeusz Błaszkiewicz poświęcił kaplicę, którą byłą drewniana stodoła. Ówczesny proboszcz śp. ks. Adam Michalski rozpoczął wtedy nieustanną adorację Najświętszego Sakramentu. Tydzień później ordynariusz przemyski bp Ignacy Tokarczuk odprawił w prowizorycznej kaplicy pierwsza Mszę Św. rezurekcyjną.

Budowę kościoła rozpoczęto w nocy z 8 na 9 czerwca 1979 roku. Rano konstrukcja belkowa była już gotowa. Prace budowlane prowadzone były w czasie trwającej wtedy pierwszej pielgrzymki Ojca Świętego Jana Pawła II do Polski. Kształtem drewniana świątynia przypominała pasterski szałas.

22 listopada 1979 roku z katedry przemyskiej wyruszyła procesja z obrazem Matki Bożej Częstochowskiej. O godzinie 19.00 bp pomocniczy Stanisław Jakiel odprawił uroczystą Mszę świętą dziękczynną.

W 1995 r. nastąpiła zmiana proboszcza, którym został ks. Marian Koźma. Drewniany kościół służył ludziom przez 20 lat. W 1998 r. przystąpiono do budowy nowej, większej świątyni. Kamień węgielny pod nią poświęcił przez Jan Paweł II w Krośnie 10 czerwca 1997 roku. Natomiast 27 września 1998 roku abp Józef Michalik dokonał jego wmurowania. Obok kamienia został wmurowany akt erekcyjny.