Pierwsza informacja o Puszczy pochodzi z dokumentu z 1242 r., kiedy jeszcze nazywano ją "Las Kłaj". W 1393 r. występuje już pod nazwą "Las Niepołomicki", a w 1441 r. użyto po raz pierwszy nazwy "Puszcza Niepołomicka".
Przymiotnik "Niepołomicka" pochodzi od staropolskiego słowa niepołomny, które oznaczało coś twardego, niezniszczalnego. Przez cały okres dziejów Polski puszcza była własnością państwa – najpierw królów Polski (XIII–XVIII w.), a po rozbiorach przeszła na własność Skarbu Państwa. Przez wieki puszcza była znakomitym terenem łowieckim, z którego korzystali królowie polscy.
Leśną drogą zwaną Królewską udawali się na polowania w głąb puszczy m.in.: Kazimierz Wielki, Władysław Jagiełło, Zygmunt Stary, Zygmunt August, Stefan Batory, August II Sas. Polowano tu wtedy na grubą zwierzynę: niedźwiedzie, dziki, tury, łosie, jelenie, żubry czy wilki.