In 1871, Melville C. Brown was appointed “Superintendent of Construction of the Penitentiary for Wyoming Territory.” Brown oversaw a lengthy bidding process that included accusations of favoritism and fraud. Promising to give the merchants of Laramie an “opportunity to bid.” Judge Brown finally awarded the construction job on April 14, 1872, to Samuel Livingston and George Schram of Denver for $31,450. Then, on July 15, some of Laramie’s citizens laid the cornerstone, placing in it mementoes such a copies of local Newspapers, speeches by natonal politicians, merchants’ business cards, photographs of Laramie’s leading society, and a bottle of old bourbon. The gathering dedicated the building to “evil doers of all classes and kinds.” The first phase of construction took just six months to complete.

The original penitentiary included only the north wing and kitchen addition of the existing structure. It contained 42 brick cells on three tiers. Walls were of stone masonry two feet thick and a massive steel and wood plank door measuring 4x8 feet formed the entrance. Barely seven months after the first prisoners arrived, much of the original woodwork and roof were destroyed in a fire resulting from faulty construction of one of the chimney flues.

In 1875, convict labor built the warden’s quarters of stone quarried from the banks of the Big Laramie River outside the prison grounds. That same year saw improvements of the addition of a 12 foot high stockade to reduce the number of escapes, an irrigation canal, brickyard, and ice house. Then, in 1889, the capacity of the penitentiary was doubled with the addition of the central area and south wing. In 1892, the first wing of the broom factory was built with additions following in subsequent years.