Yellowstonen alueen asuttaminen alkoi todennäköisesti jo melko pian jäätikön vetäydyttyä sieltä, 14 000–12 000 vuotta sitten. Ensimmäiset asukkaat olivat metsästäjä-keräilijöitä.[1] Puistosta ei ole löytynyt aineistoa, jonka avulla alueen varhaiset asukkaat voitaisiin yhdistää tiettyyn intiaaniheimoon. Intiaanien suullisesta perinteestä on löytynyt kuitenkin yhteyksiä puistoon. Flatheadit väittävät esi-isiensä asuneen siellä, ja shoshonit ovat omien sanojensa mukaan peräisin alueelta. Yellowstonen alueen käyttö lisääntyi 3 000 vuotta sitten.[2]

Lewisin ja Clarkin retkikunta kulki Yhdysvaltain poikki vuonna 1805, mutta he ohittivat Yellowstonen pohjoisesta nykyisen Montanan puolelta eivätkä pysähtyneet tutkimaan sitä.[3] Todennäköisesti ensimmäinen valkoihoinen, joka kävi puiston alueella oli John Colter, joka oli kuulunut Lewisin ja Clarkin retkikuntaan. Hän kävi alueella joko syksyllä 1807 tai talvella 1808. Hänen reitistään ei kuitenkaan ole varmuutta, ja mahdollisesti hänen näkemänsä kuumat lähteet olivatkin Codyn alueella eikä nykyisen puiston rajojen sisäpuolella.[4] Kun hän kertoi löydöksestään, hänen puheitaan pidettiin hourailuna ja aluetta pelkkänä mielikuvituksen tuotteena. Aluetta alettiinkin pilkkaavasti kutsua nimellä Colter's Hell, Colterin helvetti.[5][6]

 

Ferdinand Vandeveer Hayden piirtämä Yellowstonen kartta vuodelta 1871.

Seuraavan 40 vuoden ajan alueella metsästäneet ihmiset kertoivat lukuisia tarinoita alueen kiehuvasta mudasta, höyryävistä joista ja kivettyneistä puista ja eläimistä, mutta puheita pidettiin pelkkinä tarinoina.[7] Yhdysvaltain voitettua Meksikon–Yhdysvaltain sodan maassa heräsi kiinnostus sen syrjäseutuja kohtaan. Sisällissota kuitenkin viivytti monia suunnitelmia.[8]

David E. Folsomin kolmimiehinen retkikunta tutki Yellowstonen aluetta 1869. He olivat siviilejä, vaikkakin Folsomilla oli jonkun verran työkokemusta maanmittaajana. Retkikunta muun muassa mittasi ensimmäisenä Yellowstonen putousten korkeuden. He parantivat myös alueen karttoja, julkaisivat artikkelin retkestä Western Monthly Magazinessa 1870 ja näin innostivat seuraavia tutkimusmatkailijoita alueelle. Samana vuonna alueelle lähti Henry D. Washburnin johtama 19-henkinen retkikunta. Retkikuntaan kuului myös asianajaja ja kirjailija Cornelius Hedges, joka ensimmäisten joukossa ehdotti alueen julistamista kansallispuistoksi.[4]

Washburnin retkikuntaan kuulunut Nathaniel P. Langford luennoi heidän löydöksistään, ja yhtä luentoa oli ollut kuulemassa geologi Ferdinand Vandeveer Hayden, joka oli yksi hiljan perustetun Yhdysvaltain geologian tutkimuskeskuksen johtajista. Hayden onnistui saamaan Yhdysvaltain kongressilta 40 000 dollarin tuen retkikunnalle, joka lähti 1871 tutkimaan aluetta.[9] Mukana retkellä oli muun muassa kasvi- ja eläintieteilijöitä sekä geologeja ja myös taiteilijat William Henry Jackson ja Thomas Moran, jotka ottivat valokuvia ja maalasivat Yellowstonen maisemia. Ne liitettiin mukaan raporttiin, joka annettiin kongressille. Kongressi päätti raportin perusteella vetää maa-alueen pois julkisesta huutokaupasta, ja presidentti Ulysses S. Grant julisti alueen valtion omaisuudeksi.[4]

 

Presidentti Ulysses S. Grant, Yellowstonen perustaja.

Yellowstone on maailman ensimmäinen ja vanhin kansallispuisto. Yhdysvaltain 18. presidentti Ulysses S. Grant perusti sen 1. maaliskuuta 1872. Hän määräsi puiston intendentin virkaan Yellowstonen tutkimusretkikuntiin kuuluneen Nathaniel P. Langfordin.[10] Langford oli virassa viisi vuotta. Hän ei saanut työstään palkkaa, eikä puisto saanut juurikaan tukea. Langford vieraili Yellowstonessa vain kahdesti viiden vuoden aikana.[11] Hänellä ei ollut myöskään minkäänlaista oikeudellista mahdollisuutta suojella puiston luontoa ja geologisia muodostelmia. Hän joutui eroamaan poliittisen painostuksen takia 1877, kun häntä syytettiin puiston laiminlyönnistä.[12]

Langfordin eron jälkeen intendentin paikalle tarjoutui Philetus Norris, joka oli omin silmin nähnyt puiston kärsimän vandalismin. Hän sai paikan, ja kongressi alkoi jopa myöntää hänelle sekä palkkaa että pieniä varoja puiston hoitamiseen. Norris käytti rahoja muun muassa teiden rakentamiseen, jotta puistoa pystyttäisiin tutkimaan entistä paremmin ja tehokkaammin. Teiden oli myös tarkoitus helpottaa pääsyä puistoon. Varojen avulla Norris palkkasi lisäksi metsänvartijoita estämään metsästystä ja pitämään silmällä vandaaleja. Varoja ja henkilökuntaa oli kuitenkin yhä liian vähän puiston täydelliseen, tai edes toimivaan, suojelemiseen.[13] ?

 

Philetus Norris

Yhdysvaltojen poikki rakennettu rautatie valmistui 1880-luvulla, ja Northern Pacific -rautatieyhtiö rakensi aseman aivan puiston pohjoisen sisäänkäynnin luokse. Rautatie lisäsi ihmisten liikkumista, ja puiston kävijämäärä nousikin yli 5 000 kävijällä vuoteen 1883. Salametsästys ja puiston tuhoaminen kuitenkin jatkuivat kenenkään estämättä, ja kongressi päätti 1886 olla tukematta puiston vartijoita. Sisäministeriö pyysi armeijaa auttamaan puiston vartioimisessa, armeija otti tilanteen haltuunsa, kun se saapui Yellowstoneen vielä samana vuonna. He rakensivat itselleen majapaikaksi Camp Sheridanin, jonka lähelle aloitettiin 1891 nykyisen Fort Yellowstonen rakentaminen. Nyt rahoitus ja työvoima olivat kunnossa, ja puiston tarkka valvonta kyettiin aloittamaan. Armeija määräsi tarkat säännöt, joita oli noudatettava, jos puistossa halusi vierailla.[14] Armeija johti puistoa aina vuoteen 1918, jolloin kaksi vuotta aiemmin perustettu Yhdysvaltain National Park Service (NPS) otti puiston hoitoonsa.[11] Samana vuonna Yellowstoneen saapuivat ensimmäiset metsänvartijat, joista osa oli entisiä armeijan sotilaita. Ensimmäinen uuden hallinnon intendentti oli Horace M. Albright.[15]

Puiston rajoja siirrettiin ensimmäisen kerran 1929, kun siihen liitettiin kivettyneen metsän alueen luoteisnurkasta ja Lamarjoen latvan idästä. Kolme vuotta myöhemmin pohjoisrajaa laajennettiin vapitien tärkeälle talvialueelle.[16]

1900-luvulla autoliikenne lisääntyi, mikä lisäsi jälleen kävijöiden määrää. Vuosina 1933–1941 Yellowstoneen rakennettiin majataloja, retkeilyalueita ja ennen kaikkea pysäköintialueita niille tuhansille autoille, joita matkailijat mukanaan toivat. Toisen maailmansodan aikana kävijämäärät laskivat. Samalla valtion rahavarat ohjattiin sotatoimiin, joten Yellowstonen kunnossapitoon ei riittänyt rahoja ja jotkut aloitetut työt jouduttiin keskeyttämään sodan ajaksi.[17] Sodan jälkeen Yhdysvaltain kansallispuistojen kävijämäärät lähtivät kasvuun, ja Yellowstonessa saavutettiin miljoonan vuosittaisen kävijän raja 1948. Laman ja sodan takia puiston infrastruktuuri oli rappeutunut, ja NPS aloitti 1956 Mission 66 -projektin, jonka päämääränä oli kunnostaa kansallispuistoja.[18]

Vuonna 1988 puiston historian suurimmat metsäpalot piinasivat Yellowstonea. Huhti-toukokuussa puisto sai vielä normaalisti sateita, mutta kesäkuussa alkoi kova kuivuus. Heinäkuussa puistossa oli useita paloja, ja kuun lopulla kuivuus ja kova tuuli olivat tehneet osista paloista ja hallitsemattomia. Elokuun 20. päivänä voimakkaat tuulenpuuskat levittivät tulen hetkessä 607 neliökilometrin kokoiselle alueelle. Palot kestivät monta kuukautta, ja vasta talven lumisateet sammuttivat liekit. Lähes 36 prosenttia puistosta kärsi tulipalojen seurauksena vahinkoja.[19]

 

Roosevelt-kaari Montanassa

Monet Yhdysvaltain presidentit ovat vierailleet hallintokaudellaan Yellowstonessa. Muun muassa presidentit Chester A. Arthur ja Bill Clinton kävivät aikanaan puistossa. Puiston kannalta merkittävin arvovaltaisista vierailijoista oli kuitenkin presidentti Theodore Roosevelt, joka vieraili puistossa huhtikuussa vuonna 1903. Vierailullaan hän asetti kulmakiven silloin vielä rakenteilla olleeseen puiston pohjoiseen sisäänkäyntiin, jolle valmistuessaan annettiin nimeksi Roosevelt-kaari (engl. Roosevelt Arch). Kaaren suunnitteli Robert C. Reamer, ja sitä rakennettiin helmikuusta elokuuhun vuonna 1903. Kaaren yläosaan on kaiverrettu sanat ”For the Benefit and Enjoyment of the People”, mikä vapaasti suomennettuna tarkoittaa suunnilleen "kansan hyödyksi ja nautinnoksi".[20]

Yellowstonen kansallispuisto on kuulunut vuodesta 1978 lähtien Unescon maailmanperintöluetteloon.[21]