Teren parku był odwiedzany przez ludzi od około 10 tys. lat[1]. Początkowo były to grupy koczowników zajmujących się zbieractwem i łowiectwem, docierające do parku od północno-zachodniej strony. Jednak nie budowali oni stałych siedzib i dopiero około 2 tys. lat temu zaczęli się oni prowadzić bardziej osiadły tryb życia związany ze początkami hodowli i uprawy roli. Ludzie ci byli przodkami współczesnych Indian Pueblo i reprezentowali kulturę Anasazi (Park Narodowy Mesa Verde) oraz Fremont[1]. Za koniec kultury Anasazi uważa się rok 1300, kiedy okres tzw. Wielkiej Suszy (1230 r. n.e. - 1280 r. n.e.) prawdopodobnie spowodował przejście ludności w okolice północno-wschodniej Arizony oraz na południe do doliny rzeki Rio Grande[2]. Kolejnymi tubylcami byli Ute i Pajutowie (od około 800 r. n.e.) oraz Nawahowie (od około 1300 r. n.e.), którzy zamieszkiwali te tereny do czasów współczesnych[1].

Pierwszymi Europejczykami, którzy dotarli do terenów współczesnego parku, byli hiszpańscy księża Escalante oraz Dominguez. Poszukiwali oni dogodnej drogi z Nowego Meksyku do Kalifornii[3]. Jednak ze względu na bardzo zróżnicowaną rzeźbę terenu nie udało im się znaleźć odpowiedniego szlaku. Krótko później, w 1829 roku[4], podjęli się tego handlarze z Taos oraz Santa Fe i na początku XIX wieku wytyczyli trasę nazwaną Old Spanish Trail, wiodącą przez Moab (wzdłuż obecnej drogi US 191) oraz Green River. Trasa ta szybko stała się jedną z bardziej znanych[3][4]. Pierwszymi Europejczykami, którzy eksplorowali Canyonlands, byli prawdopodobnie amerykańscy i francuscy traperzy, podążający wzdłuż rzek w poszukiwaniu wydr i bobrów. Świadczy o tym między innymi wydrapane na skałach nad rzeką Green River przez jednego z nich nazwisko i data (Denis Julien, 1836 rok). Pierwszą oficjalną wyprawę prowadził w roku 1869 major John Wesley Powell, który w czasie trzymiesięcznej wędrówki z Wyoming do Wielkiego Kanionu stworzył pierwsze mapy oraz opis historii tego rejonu[3].

Wraz z rozwojem amerykańskiego programu nuklearnego w latach 50. XX wieku bardzo wzrosło zapotrzebowanie na uran[5][6]. Geolodzy byli przekonani, że rejon Canyonland obfituje w ten pierwiastek, a ponadto, że dostęp do złóż nie powinien być trudny ze względu na erozję[5]. Dla ułatwienia dostępu Komisja Energii Atomowej USA zbudowała prawie 1600 km dróg na południowym wschodzie stanu Utah[5]. Jedna z nich stanowi bardzo popularny trzydniowy szlak samochodowy (White Rim Road), biegnący wokół części Island in the Sky[5][6]. Niektóre z warstw skał w parku zawierają rudy uranu[6], jednak – podobnie jak w niedalekiej Monument Valley – wydobycia tu ostatecznie nie prowadzono lub trwało ono krótko.

W latach 50. i w początku lat 60. XX wieku ówczesny superintendent Arches National Monument Bates Wilson prowadził intensywne starania, mające doprowadzić do utworzenia nowego parku narodowego[7]. W 1962 roku Departament Zasobów Wewnętrznych USA opublikował pracę z propozycją utworzenia Canyonlands National Park. W dniu 12 września 1964 roku prezydent Lyndon B. Johnson podpisał ustawę tworzącą ten park narodowy[8]. W 1971 roku park rozszerzono, przyłączając rejon The Maze oraz kaniony Davis i Lavender, w wyniku czego jego obszar powiększył się do obecnych rozmiarów[7].