When the first colonists arrived at South Australia in late 1836, any prisoners (there were few at first) were held in irons aboard the ships HMS Buffalo and then Tam O'Shanter.

In early 1837 the public were warned that escaped convicts from New South Wales may reach the colony and in mid-1837 Buffalo and Tam O'Shanter sailed away.

Meanwhile, the governor's guard of Royal Marines held prisoners in their encampment in the present Botanic Gardens, chained to a tree.

As the population expanded, a temporary lock-up became necessary, which was built in early 1838 near Government House, Adelaide (then a mere hut) so the marines could guard both prisoners and Governor John Hindmarsh.

[2] In 1838, the first sheriff, Samuel Smart, was wounded during a robbery that led to one of the offenders, Michael Magee, becoming the first person to be hanged in South Australia on 2 May 1838.

Long term prisoners were sentenced to transportation in the eastern penal colonies, escorted there by police on inter-coastal ships.

When Governor George Gawler arrived he was appalled at the conditions, saying that security was only being maintained by an "expensive multiplicity of sentries".

Although Governor Gawler was under orders from the Select Committee on South Australia in Britain not to undertake any public works, in 1840 George Strickland Kingston was commissioned to design a permanent Gaol to hold 140 prisoners.

Proceedings of the Select Committee indicate that in Britain nothing was known of the gaol's construction and there is no record of any mention in any official dispatches from South Australia.

By March 1841 the goal was nearing completion, the builders Borrow and Goodiar had already received £l0,950 and they now requested a further £8,733 which Gawler refused.

As Gawler had kept no documentation whatsoever regarding the contract it could not be determined who was responsible and Kingston's appointment was later terminated on 4 August, six days after the gaol was completed.

In early September the valuation was completed with the value of work estimated at more than £32,000 above the sum already paid, which the court awarded to Borrow and Goodiar.

On 5 November the builders submitted a claim for the £32,000 plus interest, commission, legal costs and arbitration fees of more than £4,000 (2011: $9,666,000 in total).

The cost blow out to approximately £40,000 (2011: $10,740,000), being a fifth of the total funding for the establishment of the newly settled colony was the main cause of a statewide depression and numerous bankruptcies.

Following public protests over the unsanitary conditions at both Yatala Labour Prison and Adelaide Gaol, extensive renovations were carried out in 1954–55.

A toilet block was constructed in 4 and 6 yards and a semi-circular wall built in "The Circle" to allow more privacy for visits.

Previously, prisoners would line up toeing a brass rail in the Sally port of the main gate with visitors standing opposite and no closer than 2 metres (6.6 ft) which required the raising of voices to be heard over adjacent conversations.

The Deputy Keeper's residence, built in 1963, was later considered not in keeping with the overall architectural style of the complex and demolished in October 2009.

The Gaol has a radial plan which means access is gained to all the cellblocks and exercise yards from one central point.

The set-up for the New Building was slightly different in that buckets were left by one of the doors leading out and picked up prior to prisoners returning to their cells in the evening.

Until an Act of Parliament in 1858 mandated private executions, seven hangings were held in public outside the gaol gate with the first occurring in November 1840 while the site was still under construction.

The first three executions took place in the parklands west of Montefiore Hill, and the final 2 were hanged together in the original police barracks that still stand off North Terrace.

In 2007, a volunteer fell through rotting floorboards in a yard 2 building formerly used as the Prison officers recreation area and tea room.

Underneath the floor were found the remains of a previously unknown building which resulted in a two-year archaeological investigation.

It had long been suspected that South Australia's first settlers had camped somewhere along the River Torrens while waiting for the city to be laid out.

Objects found include animal bones, ceramics, glass, metal, buttons and a child's tooth.

Objects found include scraps of metal, iron, broken bricks, mortar, buttons and animal bone from the workers meals.

All students have the opportunity to explore the courtyards and jail cells, touch artifacts such as handcuffs and escape ropes and contemplate the dark history of South Australia.

The gardens are now a source of fruit, vegetables and flowers donated for use in meals for the homeless and food hampers for the needy.