In 1874, the Washington Territory legislature passed a bill which transferred all individuals convicted of felonies into a prison run by private contractors. The prison was built in Bucoda, WA, formerly known as Seatco, and in exchange for housing the men, the contractors were allowed to use them as unpaid laborers. As news of the poor conditions and abuse that occurred in the prison began to circulate, a growing public outcry led the territorial legislature to begin building Washington Territory's first prison. In 1886, lawmakers appropriated 96,000 dollars for the purchase of land and the construction of the buildings in Walla Walla, WA. The first prisoners arrived at the new penitentiary in 1887, and by 1901 it was designated as Washington State's maximum-security institution.

Throughout the first half of the twentieth-century, the Washington State Penitentiary was severely overcrowded, and prisoners were often confined in small steel cells all day. The inhumane conditions were frequently covered in the media, and contributed to several destructive riots. In February, 1957, Bobby J. Rhay became the warden of the Walla Walla Penitentiary. Following a series of reforms mandated by Governor Daniel J. Evans and Director of Institutions, Dr. William Conte between 1969 and 1970, Rhay worked to enact changes that radically transformed life at the penitentiary. Some of the reforms included the end of mail censorship, the right for prisoners to dress in their own clothes, fair hearings for rule infractions, and an elected inmate council that had a voice in the governance of the institution. The Walla Walla Penitentiary received national attention for these radical and experimental reforms. In the early 1980s, increasing violence among prisoners and guards, combined with changing philosophies about the purpose of incarceration, resulted in an end to the reforms.