Established in 1872, Yellowstone National Park had been selected by the Park Service to be the inaugural project for Mission 66 since it was the first national park. Like most national parks, planning for new building projects started well before the introduction of Mission 66 in the 1950s but received funding when the Eisenhower administration approved the ten-year program which aimed at upgrading park infrastructure in response to the post-World War II visitor boom. In February 1956, the Park Service signed a contract with the Architectural firm Welton Becket & Associates from California; by June, the park broke ground for Canyon Village. Due to the severity of Yellowstone National Park winters, planning and construction periods were narrow. Part of the construction plans included 300 cabins that would be used as motel rooms. Due to a $1 million budget mistake, Welton Becket & Associates and the Park Service increased the number of cabins to 512 to try to create more revenue for the park and recover from the budget fault.
The dedication ceremony of the Canyon Visitor Center took place in August 1957, and the Canyon Lodge opened shortly after. After opening, the Canyon Visitor center operated until 2006 when it closed for renovations. The Park Service had the cabins demolished in 2013 to make room for a modern hotel.
The original Canyon Village Lodge featured a mid-century modern architectural style adapted to the natural surroundings of Yellowstone National Park. Little of the original Canyon Lodge remains today. To accommodate for an increase in visitors, renovators relocated restrooms outside, allowing more space inside for seating and visitor traffic throughout the building. The original structure had been constructed with stone, concrete, wood, and glass. Xanterra Parks and Resorts renovators relocated a bar in the dining area in 1964 and covered the wooden floors with carpet in 1985. Translucent walls were replaced by concrete, and all the original furnishings have been removed, except for one couch. Original features including fireplaces and wooden mantels have survived the renovations and add a touch of history to the interior of the space. The glass walls have remained unaltered as well. On the exterior, new roofing plans have been in the works to add flat roofs, but the architects are concerned about snowfall buildup causing a collapse. For now, the pitched roofs remain. The Yellowstone National Park Canyon Village Lodge still serves as one of the main stops in the park for visitors to relax and find a bite to eat.