Zielonki należą do starych podkrakowskich wsi. Choć pierwsza wzmianka o nazwie „Zielonki” pochodzi z 1270 r. to jednak osadnictwo rozwijało się tu już od tysiącleci, o czym świadczą liczne odkrycia archeologiczne, dokonane np. w trakcie budowy fortów austriackich i cegielni. Wiadomo, że zanim pojawiła się nazwa Zielonki, która powstała od terenów zielonych i łąk, z wolna powstające tu osady nazywano od płynącej rzeki Prądnikami. Z czasem powstawały większe skupiska chałup przybierając odmienne nazwy. Dzięki osadzeniu wsi na prawie niemieckim, zyskiwała ona pierwszego sołtysa. Wytyczano także centrum wsi, czyli nawsie, gdzie był publiczny plac i studnia. Dzielono też pola.

Osadnictwo rozwijało się dzięki dobrym glebom i rzece Prądnik, zwanej tu Białuchą. Nazwa wzięła się od przebijającego się tu dawniej dna, utworzonego z białych skał wapiennych. Mówiono też o niej: „robotno rzeka”. Wartki nurt Prądnika wykorzystywano do napędzania urządzeń przemysłowych – młynów zbożowych, foluszów i blechów do pilśnienia i bielenia płótna, hamerni do wytwarzania blachy, prochowni i szabelni. Proch i szable z okolicy Zielonek zyskiwały uznanie również poza granicami Polski. Jak ukazuje to mapa austriacka z 1848 r. od dawna Zieleńczanie budowali swe zagrody tuż nad Białuchą, która była ważnym elementem ich codziennego życia.

Większa część Zielonek od średniowiecza stanowiła własność polskich królów, a miejsce, gdzie przed 1325 r. stanął drewniany kościół, należało do krakowskiej kapituły katedralnej. Folwark wielkorządowy, czyli królewski, został założony na wzgórzu Marszowiec. Wśród jego dzierżawców był m.in. Włoch o nazwisku Montelupi. Miał on również swą posiadłość tam, gdzie obecnie znajduje się areszt śledczy w Krakowie. Miejsce to od zawsze było ponure, skoro tam stały miejskie szubienice i świeciła latarnia umarłych (stąd przysłowie Przez Długą ulicę wprost na szubienicę).

Zielonki przynosiły swym właścicielom bogactwo dzięki licznym młynom wodnym, których bywało kilka. Obszar tutejszej parafii był również skupiskiem piekarzy, którzy od czasów nowożytnych śmiało konkurowali z krakowskimi piekarzami w sprzedaży chleba. Zdolniejsi chłopi niekiedy osiedlali się w mieście, jak czapnik Wojciech Zieleński z Zielonek (1575), który zapewne przybrał swe nazwisko od miejsca pochodzenia.