Согласно археологическим данным люди начали жить на территории, которую сейчас занимает парк, по крайней мере 11 000 лет назад. Современные исследователи впервые появились в регионе в 1805 году (экспедиция Льюиса и Кларка), а в 1807 году Джон Колтер, участник экспедиции, обнаружил геотермальные источники. Сообщения об источниках и гейзерах считались недостоверными вплоть до 1860-х годов, когда научная экспедиция Дэвида Фолсома в 1869 году поднялась вдоль реки Йеллоустон к озеру Йеллоустон. За ней последовали сразу несколько экспедиций, и в 1872 году президент Улисс Грант подписал закон, устанавливающий природоохранную зону — первый в США национальный парк — в местности около озера Йеллоустон[1]. Широкую известность природные достопримечательности парка получили благодаря картинам художника Томаса Морана, в честь которого позднее названа одна из гор в Йеллоустоне.

Первым суперинтендантом парка был назначен Натаниэль Лэнгфорд. Ему не было выделено достаточно ресурсов (ему даже не платили зарплату), и в результате браконьерство стало настолько серьёзной проблемой в парке, что Лэнгфорд вынужден был уйти в отставку в 1877 году. Его преемник, Филетус Норрис, добился того, что Конгресс США, наконец, выделил денежные средства для парка. В частности, на эти деньги были построены дороги и первые туристические объекты. В 1880-е годы к северному выходу (а в 1908 году к западному выходу) была подведена железная дорога, что существенно увеличило количество посетителей (железнодорожное сообщение было закрыто в 1960-е годы)[2].

Для борьбы с браконьерством и разрушением природных памятников в 1886 году в парк прибыли части армии США, построившие поселение Кэмп Шеридан (позже переименованное в Форт Йеллоустон) около Мамонтовых горячих источников. В 1916 году была создана Служба национальных парков США, использовавшая опыт армии в управлении парком. 31 октября 1918 года национальный парк Йеллоустон был передан в её подчинение.

Во время Великой депрессии для искусственного увеличения занятости были созданы специальные гражданские части (Гражданский корпус охраны окружающей среды), в задачи которых, среди прочего, входило создание туристической инфраструктуры в национальных парках. С 1933 по 1941 год они построили информационные центры, кемпинги и современную сеть асфальтированных дорог. После краткого упадка в 1940-е годы, связанного с войной, число посетителей вновь увеличилось. Для расширения инфраструктуры управлением национальных парков в 1956 году была принята десятилетняя программа развития, «Миссия 66[en]». Последний по времени туристический комплекс, Кэнион Вэлли, был построен в 2006 году.

26 октября 1976 года национальный парк Йеллоустон был признан международным биосферным заповедником, а 8 сентября 1978 года включён в список Всемирного Наследия ЮНЕСКО (под номером 28, среди первых объектов списка).

В 1995 году в Йеллоустонском национальном парке на волю были выпущены четырнадцать волков.