W 1376 roku wieś była wzmiankowana jako Najna lub Nana, a w 1430 roku Niebieszczany były lokowane przez Fryderyka z Miśni, na prawie niemieckim. W 1451 roku Jan Myssnar syn Fryderyka z Jaćmierza, ufundował uposażenie parafii w Niebieszczanach, a w 1461 roku uposażył parafię o kolejne dotacje. Po Jaćmirskich właścicielami Niebieszczan byli Drohojowscy, protestanci. Od 1559 roku Stanisław Drohojowski zamienił kościół w Niebieszczanach i wiele kościołów w ziemi sanockiej na zbory kalwińskie. W 1621 roku na mocy wyroku sądu królewskiego w Lublinie, katolicy w Niebieszczanach odzyskali kościół.
W 1712 roku zbudowano następny drewniany kościół, który w 1745 roku konsekrował bp Wacław Hieronim Sierakowski, pw. św. Mikołaja Biskupa. W 1895 roku kościół został wyremontowany. W 1925 roku zbudowano obecny murowany kościół w stylu neogotyckim, który w 1925 roku został poświęcony. W 1937 roku na terenie parafii było 2 243 rzymsko-katolików (w tym: Niebieszczany – 1 896, Prusiek – 343), 470 grekokatolików i 8 Żydów.
W kościele znajduje się ołtarz główny z XVII wieku przeniesiony ze starego drewnianego kościoła, odnowiony w 1972 roku przez Stanisława Filipa i Macieja Kauczyńskiego. Z dawnego kościoła zachował się jeszcze m.in. krucyfiks z 2 ćw. XV wieku oraz późnobarokowe rzeźby.