Historia wsi
Od średniowiecza Kościelniki przynależały do parafii pod wezwaniem Wszystkich Świętych w Górce Kościelnickiej.
Wieś pierwszy raz wzmiankowana w źródłach w 1369 jako Cosczelnyky, była własnością Goworka z Kościelnik i Rzędowic herbu Rawa. Po śmierci Goworka wieś była w posiadaniu jego żony Elżbiety Gutowskiej oraz ich syna Jana Guta. W 1384 był wzmiankowany jako właściciel części Kościelnik Stanisław Strasz herbu Odrowąż z Białaczowa starosta łęczycki, kasztelan małogojski. Na przełomie XIV i XV wieku pomiędzy przedstawicielami rodzin Gutów oraz Straszów z Białaczowa toczyło się kilku spraw sądowych dotyczących między innymi własności wsi. W 1420 był wzmiankowany staw pomiędzy Kościelnikami, a Stanisławicami. W 1424 Gutowie sprzedali Spytkowi z Melsztyna całą swoją część wsi z młynem, sadzawką, ogrodem i łąką. W 1427 wieś była w posiadaniu Jana Strasza z Białaczowa (zm.1440) właściciela między innymi sąsiednich wsi Stanisławic, Wolicy. W 1431 właściciel wsi Jan Strasz został oskarżony o zniesławienie królowej Polski Zofii Holszańskiej, którą publicznie posądził o cudzołóstwo. Według relacji Jana Długosza w 1470-1480 wieś była w posiadaniu Mikołaja Strasza Zakrzowskiego. Znajdował się tu rozległy łan kmiecy oraz zabudowania dworskie i folwarczne, położone w pobliżu skrzyżowania dzisiejszej ul. Pysocice oraz ul. Dybowskiego.
W 1489 Abraham Strasz Białaczowski dokonał zamiany dóbr z przedstawicielem bardzo wpływowego w Małopolsce rodu Kurozwęckich, Krzesławem z Kurozwęk herbu Poraj (około 1440-1503). W wyniku transakcji dobra Kościelniki, Stanisławice, Wolicę, Cło oraz część Rzędowic nabył Krzesław z Kurozwęk przywódca ówczesnego obozu możnowładców małopolskich, biskup włocławski, sekretarz królewski, kanclerz Królestwa Polskiego. Na początku XVI wieku wieś była w posiadaniu Mikołaja Kurozwęckiego (zm.1507), zwanego Wrzód, wojewody lubelskiego, następnie była w rękach starosty szydłowskiego Hieronima Kurozwęckiego (zm.1519/1520).
W skład klucza kościelnickiego wchodziły Kościelniki, Górka Kościelnicka, Stanisławice, Cło, Wolica (Wola Stanisławowska). Majątek odziedziczyła po nim córka Anna z Kurozwęckich, która wyszła za mąż za Jana Włodzisławskiego (zm. 1564) łowczego sandomierskiego, przedstawiciela wpływowego rodu małopolskiego Lanckorońskich. Był on jednym z pierwszych zwolenników reformacji w Małopolsce, pełnił funkcję seniora kalwińskiego. Wieś następnie była w posiadaniu Hieronima Włodzisławskiego (zm. około1605) łowczego sandomierskiego.
W rejestrze poborowym dóbr z województwa krakowskiego z 1629 wzmiankowany był jako właściciel klucza kościelnickiego Stanisław Lubomirski (1583-1649) regimentarz wojsk koronnych, wojewoda ruski, następnie krakowski, jeden z najbogatszych ludzi w ówczesnej Rzeczypospolitej. Przez szereg lat dobra kościelnickie dzierżawił Władysław Morsztyn z Raciborska (zm.1689) bachmistrz wielicki, czyli urzędnik sprawujący zarząd techniczny kopalni, aktywny działacz sejmikowy, starosta kowalski. Pod koniec XVII wieku właścicielem Kościelnik został Stefan Morsztyn (zm. po 1736) poseł sejmowy, dyplomata, starosta duninowski, który odegrał istotną rolę w działalności konfederacji tarnogrodzkiej. Po śmierci Stefana Morsztyna wieś była w posiadaniu jego brata Andrzeja Michała Morsztyna (zm.1752), kasztelana bieckiego, sądeckiego. Następnie Kościelniki przeszły w ręce Stanisława Lanckorońskiego (1721-1760) kasztelana połanieckiego oraz jego brata Macieja Lanckorońskiego (1723-1789) stolnika podolskiego, późniejszego kasztelana kijowskiego, wojewody bracławskiego. W 1773 Kościelniki nabyła Konstancja z Dembińskich Wodzicka, wdowa po kasztelanie sądeckim Piotrze Wodzickim. W dniu 15.VI.1787 roku przybywający do Krakowa król Stanisław August Poniatowski wraz z siostrą E. Branicką, zatrzymał się w Kościelnikach. Gości podejmował Eliasz Wodzicki (zm.1805) generał wojsk koronnych, starosta krakowski.
W 1790 Kościelniki z przysiółkiem Cło liczyły około160 mieszkańców, 35 domostw, znajdował się tu pałac, browar, młyn, 3 karczmy. Po 1815 Kościelniki stały się miejscowością nadgraniczną, położoną tuż przy granicy pomiędzy Rzeczpospolitą Krakowską, a Królestwem Polskim. W latach 1815-1838 Kościelniki były siedzibą I gminy okręgowej Wolnego Miasta Krakowa w skład, której weszły pobliskie Czulice, Węgrzynowice, Wyciąże, Pleszów, Lubocza, Łuczanowice, Górka Kościelnicka, Branice z przyległościami, Ruszcza, Wadów, Krzysztoforzyce, Dojazdów, Prusy, Grębałów, Krzesławice.
W 1. połowie XIX wieku dobra kościelnickie były w posiadaniu Józefa Wodzickiego (1773-1847) późniejszego dowódcy Gwardii Narodowej w Krakowie w roku 1830, który następnie kierował pracami Komitetu Bezpieczeństwa w okresie powstania krakowskiego w 1846 roku. Następnie właścicielem wsi był Henryk Wodzicki (1813-1884) polityk, poseł na Sejm Krajowy we Lwowie, członek austriackiej Izby Panów, prezes Towarzystwa Rolniczego Krakowskiego.
W 1849 majątek nabył hrabia Stefan Potocki (1820-1891). W 1868 posiadłości kościelnickie powróciły do rodziny Wodzickich za sprawą małżeństwa Teresy Potockiej, córki Stefana Potockiego z Romanem Wodzickim (1839-1893). W 1870 Kościelniki wraz z Chałupkami, Cłem, Górką Kościelnicką, Stanisławicami liczyły 879 mieszkańców. Obszar dworski liczył 924 morgi ziemi. Gromada posiadała 627 morgów. W 1890 znajdowała się tu wzorowo prowadzona gorzelnia rolnicza oraz trzy karczmy.
Dobra kościelnickie zostały znacznie zniszczone podczas I wojny światowej. W 1931 wieś liczyła 196 budynków oraz 944 mieszkańców. Posiadłość dworska należała do Wodzickich.
W 1973 Kościelniki zostały włączone do Krakowa jako część dzielnicy Nowa Huta. Od 1991 należą do XVIII dzielnicy samorządowej Nowa Huta.