Wieś położona w województwie podkarpackim w powiecie i gminie Sanok, leży na terenach noszących historyczną nazwę "Ziemia sanocka".
Wzmiankowana po raz pierwszy w 1340 roku. Według miejscowych przekazów ostatni książę halicki Bolesław Jerzy Trojdenowicz, w obawie o swoje życie (jak się okazało słusznej, zamordowano go w 1340 r.) pod koniec życia usunął się ze stołecznych ośrodków swojego państwa i w 1339 lokował na prawie magdeburskim miasto Sanok, jako pierwsze na Rusi Halickiej oraz założył kilka wsi. Były to Jurowce, które swoją nazwę wzięły od imienia księcia (książę miał tutaj swój dwór, do którego zjeżdżał na polowania), Czerteż, który swoją nazwę wziął od ruskiego słowa "czerteżnyki" tj. rzemieślnicy (tutaj książę osadził rzemieślników obsługujących dwór książęcy) oraz Kostarowce, które swoją nazwę wzięły od określenia "kostyhrowci" - gracze w kości, komicy, artyści. Według miejscowej legendy, książę Jerzy Bolesław Trojdenowicz, miał osadzić w niej artystów pochodzących ze Śląska i Czech.
W piętnastym wieku występuje w dokumentach, jako: Kostarowcze, Costirovicze, Costyrowcze, Costirowcze, Kostyrowcze, Kostorowcze, Costorowcze i Costharowcze. Do 1772 roku Kostarowce były wsią królewską, należącą do starostwa sanockiego. W dziewiętnastym wieku, w posiadanie majątku weszli Słoneccy, którzy zamieszkiwali tu do lat czterdziestych XIX wieku. Już na początku XV wieku istniał tu folwark, niestety budynki, oprócz rządcówki, stajni i spichlerza nie zachowały się, te zaś pochodzą z XIX stulecia.
Parafia prawosławna i pierwsza kostarowska cerkiew wzmiankowana jest w 1440 r. W skład wsi wchodził oddzielny przysiółek o nazwie Meszewa, wzmiankowany jako wieś w 1390 r. Posiadający własną cerkiew prawosławną.
Obecną, drewnianą cerkiew pw. Św. Symeona Słupnika (Szymona Słupnika) wybudowano w roku 1872. Po wysiedleniu grekokatolickich mieszkańców, została przekazana parafii strachockiej i do listopada 2013 roku pełniła funkcję kościoła filialnego parafii w Strachocinie, dekretem ks. kard. Wyszyńskiego pod wezwaniem Narodzenia Najświętszej Marii Panny. Trójdzielna, zestawiona z kwadratowych członów składa się z zamkniętego trójbocznie prezbiterium, szerszej nawy, babińca zwieńczonego czworoboczna wieżą i przedsionka poprzedzającego budowlę od zachodu. Przerobione w 1931 roku dachy zdobią nad nawą i prezbiterium dwie wieżyczki sygnaturek o kopulastych, krytych blachą hełmach. Wewnątrz zachowało się oryginalne wyposażenie, w tym ikonostas z XIX wieku. W 1987 roku cerkiew została rozbudowana, inicjatorem rozbudowy był proboszcz ks. Józef Niżnik.
Od listopada 2013 roku Kostarowce są oddzielną parafią, pierwszym proboszczem został ks. Bogdan Czerwiński.
Według spisu z 1938 roku w Kostarowcach mieszkało 1040 Ukraińców (to jest grekokatolików) i 220 Polaków ( rzymskich katolików). Obecnie wieś jest jednolita etnicznie i liczy prawie 800 mieszkańców.