The following may be helpful.I think there were various jails utilized in the nations in Indian Territory prior to Oklahoma becoming a state, but not a state prison/penitentiary.
From Wikipedia, the free encyclopedia
Before Oklahoma became a state in 1907, felons convicted in Oklahoma Territory and Indian Territory were sent to the Kansas State Penitentiary in Lansing, Kansas. At statehood, Kate Barnard became Oklahoma Commissioner of Charities and Corrections. During the summer of 1908, Barnard arrived unannounced at the Kansas prison to investigate widespread complaints she had received about mistreatment of Oklahoma inmates. She took a regular tour with other visitors first, then identified herself to prison officials and asked that she be allowed to conduct an inspection of the facility. Barnard discovered systematic, widespread torture of inmates.
Upon her return to Oklahoma, Barnard recommended that all Oklahoma inmates be removed from the Lansing facility and returned to the state. Governor of Oklahoma Charles N. Haskell supported Barnard's proposal, and within two months of Barnard's visit to Kansas, on October 14, 1908, two groups of 50 offenders each were sent by train to McAlester. The inmates were temporarily housed in the former federal jail in the town. Under direction from Warden Robert W. Dick, they built a stockade to house themselves on a 120 acres (0.49 km2) plot northwest of McAlester, which was donated to the state by a group of McAlester citizens.
The remaining Oklahoma inmates in Lansing were moved to the United States Penitentiary, Leavenworth until the state could build adequate facilities to house them all. The next spring, in 1909, the Oklahoma Legislature appropriated $850,000 to build the permanent facility.