The archaeological significance of the Pictograph Cave (also known as the Inscription Cave) was first discovered in 1937 by Mr. H.S. Barringer of Billings, Montana, Mr. and Mrs. Jim Browne, then of Billings; and Mr. Oscar Lewis, then of Glendive, Montana. The cavern is a large erosional recess in a sandstone escarpment located approximately seven miles southeast of Billings, Montana. It had been known to local inhabitants, both Native American and white, as an interesting location due to the many painted pictographs of Native American origin that covered its walls.

The site was acquired by the Montana Highway Commission and excavated with labor provided by the Depression-era Works Progress Administration and River Basin Surveys. The project was initially placed under the direction of H. Melville Sayre, a geologist from the Montana School of Mines, and his crew chief Oscar Lewis, an amateur collector from Hardin, Montana. Sayre documented 106 pictographs inside the cave. William Mulloy took over the excavations in 1939 following Sayre's death.

World War II brought an end to the WPA archaeological excavation at Pictograph Cave in 1941. By that time more than eight thousand cubic meters of dirt had been dug up and sifted and over thirty thousand artifacts uncovered from the distinct cultural occupation levels. Many of the artifacts, as well as field notes and sketches made during the excavation, are now preserved at the University of Montana in Missoula.

After studying the artifacts, Mulloy suggested that the longest occupation at the site was by ancestors of the Crow Indians, who were in transition from an agricultural economy to a nomadic buffalo-hunting culture. Mulloy later used the findings at Pictograph Cave to develop a chronology of prehistoric northern plains cultures, which, for the most part, has withstood the test of time.

In the post-war years Pictograph Cave suffered. Vandals burned down the museum and defaced the pictographs with graffiti. Litter cluttered the landscape, and vegetation choked the trails. In the early 1960s the Billings Archaeological Society and city boosters started a movement to protect and promote Pictograph Cave as a tourist attraction, and in 1963 Billings mayor Willard Fraser signed an agreement with the state to manage and develop the site. Fraser declared Pictograph Cave a city park and spearheaded an effort to have it designated a National Historic Landmark, which it became in 1964. Fraser also established the Indian Caves Commission to clean up the site and design a development plan for the park, but the city council refused to allocate funds for a park outside the city limits and volunteer efforts could not quell the vandalism. In 1968 the federal government threatened to rescind Pictograph Cave's landmark status due to its continued degradation. The following year the city of Billings surrendered management of the caves to the Parks Division of the Montana Department of Fish and Game, and the site was renamed Pictograph Caves State Historic Site.

The state agency launched a program to improve and protect the park in 1972. Crews built trails, outhouses, and picnic facilities, and they installed interpretive signs, sandblasted away the graffiti that marred the pictographs inside the cave, and took steps to protect the park from further damage. Although the park continued to be a popular local picnic spot, it also began to attract a growing number of tourists. Pictograph Cave became a state park in 1991.

In the years since, growing concern over the loss of pictographs to fading and sloughing has spurred conservation efforts. Studies conducted in the 1990s identified only 44 of the 106 images that archaeologists recorded in the 1930s. Some have been obscured by a patina of mineral deposits. Others have been lost to erosion, vandalism, and earlier attempts to remove graffiti from the cave walls.