História obce Kostoľany nad Hornádom je úzko spätá z históriou hradu a obce Sokoľ. Písomná zmienka o obci Sokoľ pochádza z listiny z roku 1423. Tá slúžila ako doklad, že kráľ Žigmund dáva hrad Sokoľ Matúšovi a Imrichovi z Pavloviec. Hrad, vtedy sa nachádzajúci v Šarišskej stolici, im odovzdal so všetkým príslušenstvom, okrem obce Kavečany, ktorú dal Košiciam. K vlastníctvu hradu Sokoľ patrili obce Sokoľ (Zakolya), Kostoľany nad Hornádom (Zenthestwan), Malá Vieska (Wyfalu) a Tepličany (Tapilczan), ako aj Rokycany (Berky), Biskád (Bykzad), vyhynutá dedina neznámej polohy, Ružín (Rwsynch), Malá Lodina (Felsew Landa) a veľká Lodina (Also Landa).

Obec Sokoľ však existovala ďaleko skôr, čo potvrdzuje i listina z prvej polovice XIV. storočia. Pápežské deisatkové záznamy z rokov 1332 - 1337 potvrdzujú existenciu fary v dedine Sokoľ (Alzokole, Alzokolc). Je tu však problém s presným lokalizovaním vtedajšej obce. Na základe písomných záznamov je dôvodné nazdávať sa, že kostol Sokoľ sa nachádzal v časti, kde sú dnes Kostoľany. Predpokladá sa totiž, že kostol ležal na polceste medzi dedinami Sokoľ a Tepličany. Až neskôr začali okola kostola vznikať nové stavby - obytné domy, ktoré dali základ súčasnej obci Kostoľany. Od toho sa odvíja aj jej názov. Problematické je aj označenie hradu, pretože v rôznych dokumentoch a historických štúdiach dochádza k zámene hradu Sokoľ - Hradová, čiže tzv. košického hradu, ktorý sa nachádza pri ceste do Kavečian na hrebeni medzi Suchou dolinou a Hornádom a hradom Sokoľ, ktorý je od dnešnej obce Sokoľ vzdialený asi sedem kilometrov. Aj na turistickej mape je jeho poloha vyznačená zle. Chatrné ruiny sa nachádzajú zarastené v lese v lokalite, ktorá sa volá Na hrádku.

Skutočnosť, že kostol Sokoľ tu stál už v roku 1332, svedčí o ľudnatom osídlení lokality, takže je možné predpokladať, že aj obec Sokoľ existovala už v rokoch 1289, keď podľa historických listín už existovali dediny Trebejov a Obišovce. Dedina Sokoľ musela existovať už pre vznikom hradu Sokoľ, ktorý vznikol niekedy v rokoch 1297 - 1311 (r. 1297 ho nebolo a v roku 1311 už stál), a hrad Sokoľ dostal názov bezpochyby podľa názvu tejto dediny, kde boli kráľovskí sokoliari (falconarii), lebo v oblasti nad dedinou Sokoľom sa konali veľké kráľovské poľovačky so sokolmi. Hrad aj dedina mali svoje opodstatnenie aj z hľadiska obchodného. V obci sa platilo mýto za drevo- plte plavené po Hornáde, čo dokumentuje listina z roku 1423. V roku 1429 dostali Košice hrad Sokoľ i jeho obce. Podmienkou daru bolo, že sa hrad zrúca. V roku 1440 sa uvádza už ako ruina.

 Ako je uvedené pri zmienkach o hrade Sokoľ, obec Kostoľany nad Hornádom bola vystavaná okolo kostola, ktorý patril k Sokoľu. Preto sa aj tento kostol uvádza na pápežských desiatkoch z rokov 1332 - 1337 ako Alzkole, čiže ako Nižný Sokoľ. Kostol na pravej strane Hornádu bol vystavaný v poli medzi medzi obcami Sokoľ a Tepličany. Postupne okolo obce tamojší obyvatelia vystavali domy, až vznikla samostatná obec Kostoľany, ľudovo Kosceľany, ale i Koscelka. Pretože bol kostol zasvätený sv. Štefanovi, maďari nazývali obec Szent István.

Postupné osídľovanie územia okolo kostola možno datovať do XIV. storočia. Nastaršia správa o nej však pochádza až z 15. storočia, konkrétne z roku 1423. Ako možno vyčítať z portálneho súpisu z roku 1427, obec svojou rozlohou zaberala 9 port a jej majiteľom bol Matúš z Pavloviec.

1423 - Zenthesthwan
1427 - Zenthistwan
1429 - Zenth Istwan
1440 - Zenthestwan
1555 - Zent Istwan, Costelanka
1558 - Costellanka sive Zent Estwan
1560 - Costellani
1773 - slovensky Kosczelany, maďarsky Sz. Isztván
1808 - slovensky Kostelany
1906 - ľudovo Kosceľany

Obec bola od svojich počiatkov osídlená Slovákmi, ich kontinuita nebola nikdy prerušená. V časoch reformácie 16. storočia tu pôsobili slovenskí evanjelickí farári. V roku 1560 Jeronym, 1586-1591 Peter Lindak z Lučenca, 1595 - 1599 Daniel Fabry z Nemeckej Lupče a v roku 1620 - 1621 Pavel Wigastius. V roku 1787 mala obec 46 domov a 309 obyvateľov, v roku 1828 82 domov a 622 obyvateľov. Zaoberali sa poľnohospodárstvom a pestovaním zeleniny, koncom 19. storočia prácou v dvoch kameňolomoch.  Začiatkom 20. storočia postavili tu továreň na výrobu umelých hnojív. V roku 1959 založili v obci JRD.

Do roku 1848 patrila obec do Abovskej stolice a v roku 1924 do Košickej župy. Za krajinského zriadenia v období rokov 1928 –1938 patrila do okresu Košice – vidiek a  v rokoch 1949 – 1960 bola začlenená do Košického kraja. V roku 1960 sa Kostoľany nad Hornádom zlúčili s  Malou Vieskou a Tepličanmi a vznikla obec  Družstevná pri Hornáde. Tento stav trval 42 rokov. V roku 2002 sa uskutočnilo úspešné referendum o odčlenení obce, na základe ktorého 1. januára 2003 oficiálne  získala obec Kostoľany nad Hornádom opäť svoju samostatnosťa začala sa písať novodobá história obce...