Parafia w Nowosielcach jest jedną z najstarszych w archidiecezji przemyskiej, a jej korzenie sięgają głęboko w czasy średniowiecza. Nazwa miejscowości, oznaczająca nowe sioło, pojawiła się po raz pierwszy w dokumencie wystawionym 14 grudnia 1372 r. przez księcia Władysława Opolczyka, namiestnika królewskiego na Rusi, dla niejakiego Franczka z Marszowic za wierną służbę rycerską. Za datę erygowania parafii pw. św. Marii Magdaleny uważa się rok 1384. Wtedy także - 19 października - wdowa po znanym nam już właścicielu wsi, Katarzyna, uposaża parafię łanem ziemi, karczmą i terenem pod zabudowania plebańskie. Od roku 1630 parafia należała do dekanatu jarosławskiego, później, w poł. XVIII wieku, do archidiakonatu jarosławskiego, następnie w XIX stuleciu do kańczudzkiego, a obecnie przynależy do dekanatu przeworskiego.
Prawdziwą ozdobą parafii nowosieleckiej, ale także całej wsi jest piękny drewniany kościół, konsekrowany 28 kwietnia 1595 r. przez arcybiskupa lwowskiego Jana Dymitra Solikowskiego. Kościół wzniesiony w tradycji gotyckiej, położony na wzgórzu nad stawem, pełnił przez wieki funkcje obronne i był schronieniem dla miejscowej ludności. Posiadał fortyfikacje ziemne (wał wewnętrzny i zewnętrzny), groblę i most zwodzony. Posiada murowane fundamenty. Na jego miejscu stał zapewne wcześniej kościół wystawiony w czasach erygowania parafii, a jeszcze wcześniej obronne grodzisko. W 1624 r., w dniach 9-13 czerwca, nowosielecka świątynia przeżywała oblężenie wojsk tatarskich. W kościele schroniła się wówczas okoliczna ludność. Na kościelnej wieży ustawiono śmigownice, które obsługiwał artylerzysta wojsk koronnych, Franciszek Dudek, sam będąc już inwalidą wojennym (nogę stracił podczas walk pod Chocimiem). Obroną miejscowości dowodził wójt Michał Pyrz, na którego cześć w 1936 r. usypano pamiątkowy kopiec. Bohaterem walk był także niejaki Jaśko, który wprowadził zamieszanie w obozie tatarskim, płosząc tabun koni, a także ówczesny proboszcz Piotr Kisiel. 29 czerwca 1936 r., w czasie uroczystości odsłonięcia kopca dzielnego obrońcy Nowosielec Michała Pyrza, miała miejsce wielka manifestacja chłopska przeciwko polityce rządów sanacji, chłopi zakrzyczeli wówczas generała Edwarda Rydza-Śmigłego.
Widoczna już z daleka sylweta nowosieleckiego kościoła, usytuowanego na lekkim wzniesieniu, urzeka swoim pięknem. Świątynia o konstrukcji zrębowej nakryta jest gontowym dachem z wieżyczką na sygnaturkę, posiada nawę i węższe orientowane trójboczne prezbiterium, do którego od północy przylega zakrystia. Od zachodu do kościoła przylega wieża konstrukcji słupowej z izbicą, kryta czterospadowym dachem gontowym, na szczycie znajduje się złocony krzyż na kuli. Właśnie w wieży natrafiono swego czasu na mosiężną tablicę pochodzącą z 1631 r., z napisem w języku łacińskim, z którego wynika, że niejaka księżna Anna ze Sztembergu ofiaruje pozłacaną kulę ze złotym krzyżem na szczycie. Na odwrocie wspomnianej tabliczki wspomniano o XIX-wiecznym remoncie wieży. W wieży kościelnej w specjalnej drewnianej skrzyni przechowywano też, w czasach ataków wroga, szczególnie cenne przedmioty: monstrancję, kielichy, ornaty itp. Pod koniec XX wieku przebudowano przyziemie wieży, m.in. dostawiając kamienny przedsionek z okienkami i przyporami na narożach. Wokół kościoła dostawiono soboty, stanowiące schronienie przed zimnem i deszczem dla przybywających w soboty wieczorem wieśniaków z okolicznych miejscowości, m.in. Bud Łańcuckich, którzy oczekiwali na niedzielną Mszę św.
Wchodząc do wnętrza świątyni, zwracamy oczywiście uwagę na ołtarz główny z ok. 1773 r., w którym niedawno ponownie umieszczono obraz patronki świątyni, św. Marii Magdaleny, pędzla dziewiętnastowiecznego artysty. Święta trzyma w rękach czaszkę ludzką - symbol pokuty. W zwieńczeniu dwukondygnacyjnego ołtarza znajduje się obraz przedstawiający Ukrzyżowanie, z postaciami Matki Bożej, Marii Magdaleny i św. Jana Ewangelisty. Zwracamy uwagę na płaski sufit, ozdobiony polichromią, ściany z prostokątnymi otworami okiennymi. Wnętrze nakryte jest płaskim stropem, a dwa duże drewniane słupy podtrzymują strop.
Także w prezbiterium, po bokach ołtarza głównego, oglądać dziś możemy piękne obrazy. Po lewej stronie zawieszono zabytkowy, późnogotycki obraz Matki Bożej Nowosieleckiej, pochodzący z około 1529 r., malowany temperą na desce lipowej. Maria trzymająca Dzieciątko, otoczona owalną aureolą, wsparta jest na półksiężycu, w dolnym rogu klęczy malutka postać anonimowego duchownego. Obraz wypełnia złocone tło. Dawniej umieszczony był on w ołtarzu głównym. Po prawej stronie, w owalnych ramach obraz z XVII stulecia „Ecce Homo”, przedstawiający umęczonego Chrystusa w koronie cierniowej na głowie. Na belce tęczowej znajduje się barokowa, XVIII-wieczna Grupa Ukrzyżowania: Jezus na krzyżu z Matką i św. Janem.
Przy belce po lewej stronie oglądamy przepiękną, rokokową ambonę z II poł. XVIII wieku. Ambonę przykrywa baldachim zwieńczony wolutami, z postacią aniołka na złączeniu. Po prawej stronie belki tęczowej zaplecek z baldachimem, na którym również uskrzydlona postać aniołka, u góry kartusz z łacińskim napisem. Tutaj też ustawiono przepiękną rokokową chrzcielnicę z III ćw. XVIII wieku. Czasza chrzcielnicy podtrzymywana jest przez klęczącą postać. Na pokrywie scena przedstawiająca chrzest Jezusa w Jordanie. W prezbiterium znajdują się też czterosiedziskowe stalle z II poł. XIX wieku, ze zdobionym wicią roślinną baldachimem.
Rokokowe ołtarze boczne z XVIII wieku: ołtarz prawy - obraz serca Jezusa (XIX wiek) na zasuwie, obraz św. Mikołaja przekazującego posag trzem ubogim pannom (XVIII wiek) i w zwieńczeniu św. Antoni z Dzieciątkiem; po lewej stronie, w bocznym ołtarzu obraz Madonny w typie Hodegetrii z poł. XVIII wieku, na zasuwie Serce Marii (XIX wiek) oraz w zwieńczeniu św. Józef z Dzieciątkiem.
W kościele znajdują się też na rokokowym chórze z XVIII wieku pięknie zdobione organy, zabytkowa kropielnica z XVII wieku typu kielichowego, dębowe skrzynie z XVI wieku z okuciami żelaznymi. Na jednej ze ścian umieszczono tablicę epitafijną z 1883 r., upamiętniającą proboszczów parafii, począwszy od XVII wieku. Dzisiaj, od 2004 r., swoim parafianom służy proboszcz ks. Piotr Walasz. Na ścianach zawieszono też, wykonane techniką cynkopii siatkowej, XIX-wieczne stacje drogi krzyżowej.
Kościół był wielokrotnie remontowany na przestrzeni wieków, m.in. w latach osiemdziesiątych XX wieku. Na początku XXI wieku, podczas prac remontowych natrafiono na krypty grzebalne pod prezbiterium, w których znaleziono doczesne szczątki proboszczów nowosieleckich.