Wieś założono w roku 1352 i już w XIV w. istniała tu parafia rz.-kat. Ponowne zasiedlenie tych terenów przez ludność wołosko-ruską nastąpiło w XVI w. Wtedy powstała to parafia prawosławna (później greckokatolicka), obejmująca początkowo także Milik i zbudowano tu cerkiew. W latach późniejszych Milik rozrósł się I Andrzejówka była filią parafii w Miliku.
Obecna cerkiew jest już kolejną w tym miejscu. Być może powstała z przebudowy poprzedniej świątyni. Jest to cerkiew łemkowska, typ północno-zachodni, wariant młodszy. Drewniana, konstrukcji zrębowej, orientowana, trójdzielna. Prezbiterium kwadratowe z zakrystią od północy, szersza od niego kwadratowa nawa. Wieża z izbicą, konstrukcji słupowej o pochyłych ścianach obejmująca słupami babinbiec, z zachatą dookoła. Ściany całości obite gontem. Dachy namiotowe; nad prezbiterium z uskokami, z makowicami i pseudolatarniami, nad prezbiterium i nawą kryte blachą, nad wieżą gontem. Latarnie oraz uskoki dachów malowane w czerwone, białe i zielone wzory.
Wnętrze świątyni nakryte jest kopułami namiotowymi i ozdobione polichromią ornamentalną z XlX/XX w. Na ścianach malowidła architektoniczne, nad ikonostasem forma baldachimu. Ponad nawą przedstawienie Boga Ojca.
Ikonostas późnobarokowy z pocz. XIX w. z cennymi ikonami Matki Boskiej i św. Mikołaja. Pozostałe ikony przemalował w 1874 r. malarz z Bardiowa Victorin Zomph, z pochodzenia Niemiec. Rok wcześniej malował on ikony dla cerkwi w Leluchowie.
W nawie dwie nastawy ołtarzy bocznych w tradycji baroku z XVIII w, pochodzące z poprzedniej cerkwi. W ołtarzu południowym Ukrzyżowanie, w północnym Zdjęcie z Krzyża. W wyposażeniu dwa feretrony z obrazami z XVIII w. utrzymane w tradycji malarstwa ikonowego z przedstawieniami Matki Bożej i św. Barbary. Nietypowym elementem wyposażenia jest instrument muzyczny, obecnie nieużywany, zwany dzwonem Ewy. Tworzy go stalowa sztaba z nawierconymi różnej wielkości otworami podwieszona do stropu. Grano na nim, głównie podczas procesji, uderzając w instrument metalowymi młoteczkami.
W wieży zawieszony jest dzwon "Antoni" z 1691 r. Teren przycerkiewny otoczony jest wieńcem drzew i kamiennym murem.
Od 1947 r. świątynia służy jako kościół rz.-kat. pw Najświętszej Maryi Panny Wniebowziętej, filia parafii w Miliku. Msze św. w niedziele i święta o godz. 9:30.