Because of the early settlement of the lower Mississippi territory, the first reported prison to house felons was developed in Natchez around 1789. The first centralized prison, later to be called The Walls, was not completed until 50 years later with the opening of the penitentiary in Jackson, April 15, 1840. The Walls, located on the present site of the new capitol building was developed at a cost of $75,000, built with inmate labor and was capable of housing 200 inmates. According to historical accounts, 28 prisoners were placed in the new prison on opening day.Between 1840 and 1860, there was a shift to the use of prison labor to manufacture course-cotton fabrics, bale rope and hemp, and cotton bagging for mechanical trades. By 1852 The Walls was experiencing over crowding. With a reported population of 220 inmates. An additional 40 acres of land near the prison was purchased and over 1,300 cords of wood harvested using inmate labor. The need for manpower in the Confederate Army led the governor to pardon 40 inmates to be mustered into the ranks of the Confederate Army. Other inmates were moved into county jails so the prison could be converted into a munitions plant.  The prison fell prey to Sherman's Federal Army in May, 1863, as it swept across the south toward Atlanta.  

By 1866 architects reported that the prison was ready to comfortably house 130 state inmates. Pursuant to a legislative act in 1866, Governor B.J. Humphries reported on January 24, 1867, that the penitentiary had been leased under a $100,000 bond to J. W. Young and Company for 14 years. This move was made to hasten the rehabilitation of the war torn prison.  In 1894, the legislature appropriated $125,000 for the purchase of plantation land parcels including: 3,200 acres in Rankin County; 2,700 acres at Oakley Plantation in Hinds County; and 2,000 acres at Belmont Plantation in Holmes County. State prisoners were immediately moved to these sites. In 1900 the legislature appropriated $80,000 for the purchase of the 3,789 acre Parchman Plantation located in Sunflower County. In 1901, four stockades were built at Parchman and state prisoners were moved there to begin clearing efforts for cultivation of crops at the sprawling delta farm. Because of the unique dispersed configuration of the camps, the state penitentiary has been referred to as "the prison without walls."

On February 8, 1971, the United States District Court of the Northern District of Mississippi intervened, in the landmark class action suit Gates vs. Collier. Key Issues of Gates vs. Collier included:

• Racial segregation of inmates
• Use of corporal punishment
• Punishment of inmates
• Poor medical care for inmates
• Poor shakedown procedures
• Many inmates had weapons
• Drugs and alcohol were plentiful

In 1972, Federal Judge William Keady ordered the state to devise a plan to remedy the situation at Parchman. As a result, the following improvements were made at the penitentiary:

• Racial segregation was forbidden
• Mail censorship was curtailed
• Living conditions were greatly upgraded
• Many of the older units were closed and several new units were built
• Some existing units were renovated The facilities at the penitentiary were required to be closer to each other
• Trusty guards were replaced by correctional officers
• All forms of corporal punishment were abolished
• Inmates’ rules and regulations were established
• Formal disciplinary procedures were adopted
• Medical care was upgraded
• Better contraband control measures were undertaken

The state responded, closing the old units during the 1970’s. However, at best the new development program completed by the state was less than effective in meeting needs of a growing prison population. The new prison facilities developed in the period of the 70's included:

The new prison facilities developed in the 1970's included 3080 beds at a cost of $35,345,000. The Mississippi Department of Corrections, which was created by an act of the legislature was formed on July 1, 1976, by the merging of the Mississippi Penitentiary Board and the Mississippi Probation and Parole Board. The department began to decentralize by setting up Community Facilities and Restitution Centers. During this period, the department also began to recognize, and provide for the treatment needs of offenders.  In February 1975, the Pre Release Job Assistance Program was initiated.  The program was designed to help offenders locate employment and also provide information regarding applications, interviews and successful workplace habits.  In May 1996, the Alcohol and Drug Treatment Center was opened in recognition of, and to counter, the detrimental effects and incarceration rates related to the abuse of alcohol and drugs.

In January, 1986, the department opened the Central Mississippi Correctional Facility (CMCF) located at Pearl, Mississippi. This was the first major institutional facility to be located away from Parchman. The initial capacity was 667. All female offenders were moved from Parchman to this facility. On April 13, 1990, MDOC opened the South Mississippi Correctional Institution (SMCI), located in Leakesville, Mississippi. The original capacity at SMCI was 516.  In addition to CMCF and SMCI, the MDOC opened seventeen community work centers and four restitution centers. With the move toward regional prisons, the Department of Corrections has shifted its prison program efforts from an agricultural plantation operation to a wide variety of prison industry projects coupled with vocational training embracing a number of skills found in the free world labor market. Emphasis is also being given to providing an education for those in the prison population who demonstrate a sincere desire to learn.

On August 23, 1994, the State Prison Emergency Construction and Management Board (SPECM) was formed into law in section 47-5-1201 of the Mississippi Code of 1972, Annotated. The purpose of the board was to alleviate the immediate and the projected operating capacity needs of the state correctional system by providing for the immediate and long-term addition of correctional facilities. It was the intent of the Legislature that agencies expedite the procurement of facilities to alleviate the short-term emergency capacity needs of the correctional system.  As a result of the efforts of SPECM and the ongoing efforts of MDOC administrations, the MDOC has in operation the three state run prisons, eleven regional prisons, six private prisons, seventeen community work centers and four restitution centers. In February 1998, MDOC rectified all discrepancies in the Gates vs. Collier lawsuit.

By contract, all private and regional facilities are required to be accredited by the American Correctional Association (ACA). As of May 2003, all three state run prisons are ACA accredited.