Nie jest znany dokładny czas budowy kościoła. Według jednych źródeł jego powstanie wiązać można z uposażeniem parafii przez biskupa Piotra Chrząstowskiego w 1448 roku zaś według innych w 1482 roku. W opisie golcowskigo kościoła opracowanym przez ks. Jana Lisińskiego, na początku XX wieku, czytamy następującą wzmiankę:
Według bardzo starego aktu na pergaminie umieszczonego w zakrystii, kościół był wybudowany około 1448 roku pod wezwaniem Narodzenia Najświętszej Maryi Panny i św. Barbary Męczenniczki, a konsekrowany według tegoż aktu przez biskupa Wojciecha Baranowskiego w pierwszą niedzielę po św. Franciszku z Asyżu w 1589 r.
Kościół parafialny w Golcowej jest jednym z najstarszych zabytków późnogotyckiej architektury sakralnej na terenie Podkarpacia. Znajduje się on na Szlaku Architektury Drewnianej Województwa Podkarpackiego. Jest to kościół drewniany w stylu gotyckim, zbudowany z drzewa modrzewiowego. Przy jego budowie zastosowano system więźbowo-zaskrzynieniowo-zaczepowy należący do najstarszych typów konstrukcyjnych kościołów drewnianych. Mimo, że wielokrotnie był modernizowany, do dziś jednak zachował fragmenty dawnej konstrukcji. Na szczególną uwagę zasługuje bardzo dobrze zachowana storczykowa konstrukcja więźby dachowej.
Więźba dachowa na kościele strong>nie jest jednorodna. Nad prezbiterium i nawą zachowała się oryginalna, storczykowa więźba dachowa, z czasów budowy kościoła z 2 połowy XV wieku, nad częścią dobudowaną, przedłużeniem nawy, zachowała się również storczykowa więźba z czasów rozbudowy z 2 połowy XIX wieku.
Połączenia ciesielskie są kołkowane.
Na starszej części więźby, z czasów budowy kościoła, zachował się komplet oznakowań. Znaki ciesielskie w postaci nacięć dłutem o półokrągłym zakończeniu, długości 3 – 4 cm i głębokości ok. 0,5 cm oraz ilości odpowiadającej kolejności wiązara licząc od prezbiterium (od wschodu ku zachodowi), umieszczone są zawsze od strony wiązania i zazwyczaj w niedalekiej odległości od niego.
Nad nowszą częścią więźby znaków ciesielskich brak, widoczne są jedynie numery wiązarów (cyfry arabskie 1, 3, 5, 7) na storczykach.
Do II połowy XIX wieku kościół ulegał nieznacznym przekształceniom, nie mającym jednak większego wpływu na kształt bryły. Dopiero ok. 1872 roku rozebrano drewniane podcienia okalające budynek z trzech stron – tzw. soboty, obito go dookoła deskami, dźwignięto kościół o jedną podwalinę, wybudowano wieżyczkę na sygnaturkę oraz dobudowano kruchty.
Gruntownej przebudowy dokonano w latach 1885-87, kiedy to przedłużono nawę o 16 łokci (9,60m) w kierunku zachodnim, gontowe pokrycie dachów zastąpiono blachą, a we wnętrzu wprowadzono podział na trzy nawy za pomocą dwóch rzędów drewnianych słupów i ozdobiono wnętrze polichromią autorstwa Jana Tabińskiego.
W latach 2007 – 2009 przeprowadzono kolejny gruntowny remont bryły kościoła. Wymieniono niektóre podwaliny i lisice, wymieniono zniszczone elementy konstrukcji dachowej, zrekonstruowano nową wieżyczkę i pokryto całość dachu blachą tytanowo-cynkową oraz obito ściany budynku nowymi gontami. Wymieniono instalację elektryczną w całym kościele i zamontowano systemy zabezpieczeń przeciwpożarowych i antywłamaniowych.
W latach 2014-2018 prowadzone były intensywne prace konserwatorskie i renowacyjne we wnętrzu świątyni – polichromii i elementów ruchomych zabytkowego kościoła. W wyniku tych prac zdjęto kilka późniejszych przemalowań ścian i powrócono do polichromii Tabińskiego, natomiast na ołtarzach i ambonie odtworzono pierwotną kolorystykę.
Obecnie wyremontowany zabytkowy kościół odzyskał pierwotną świetność i blask. Jest również świadectwem kultury i sztuki minionych wieków i do dziś pełni funkcję czynnej świątyni parafialnej, w której sprawowany jest kult.
Kościół ma obecnie 28,5 metrów długości nie licząc przedsionka, a jego szerokość wynosi 9,7 metra.