Fremantle Prison, originally known as the Convict Establishment, was built by convict labour between 1852 and 1859 from limestone quarried on site. Its history, including its convict past, its use as the main place of incarceration for the state, and its current role as an important historic and tourist venue reflects in many ways the history of Western Australia.

The Swan River settlement was established as a free colony in 1829. It was slow to develop mainly due to the inhospitable nature of the land. Many lured by Captain Stirling’s glowing reports of the abundance of fertile land, left in disgust when faced with the grim reality of Western Australia’s formidable climate and conditions. The resulting small population meant there were few hands available to expand the colony beyond the early settlements around the Swan River and at Albany.

Between 1845 and 1847, York Agricultural Society, supported by several merchants, lobbied the colony's Legislative Council to petition the British Government to send convicts. They saw this as the best option to help supplement the lack of skilled and unskilled labour threatening to cripple the colony. The convicts were to provide much needed cheap labour for the building of roads, bridges, jetties and other infrastructure necessary to service the colony. For convicts who were nearing the end of their sentence a system of ticket of leave, similar to our modern day parole, was also introduced which helped provide labour for the development and expansion of agriculture.

Following a report from the colony and then debate within British government departments, an Order-in-Council was passed by the British Parliament on 1 May 1849 which stated:

that upon and from the first day of June in this present year; Her Majesty’s settlements in Western Australia shall be places to which felons and other offenders in the United Kingdom then being or thereafter to be under sentence or order of transportation or banishments shall be conveyed…

The first ship carrying convicts arrived at Fremantle on 1 June 1850. Captain Edmund Henderson was responsible for the 75 convicts on board as well as the Pensioner Guards, Warders and their families who accompanied them. The colony was completely unprepared for their arrival as the ship carrying this human cargo overtook the ship carrying the dispatch containing news of this event.

Henderson's first task was to find accommodation for his charges in the small port of Fremantle. A warehouse, leased from the Harbour Master Daniel Scott and located on the waterfront of the town, was modified to serve as temporary quarters for the convicts until a more permanent depot could be built. Accommodation for the convicts' keepers was more problematic.

After considering several alternatives including Mount Eliza, now famous as the lookout at King's Park, Henderson chose land on a limestone ridge above the town of Fremantle and was given a grant of around 36 acres. Henderson was pleased with the location and wrote to his superiors in England that:

[t]he site proposed is in every way well suited for the purpose; it is a healthy and elevated spot - removed from the business part of the town, and within convenient distance of the harbour; in the improvement of which there will be the employment for the Prisoners for many years after the Government works are complete.

The limestone of the ridge provided the building material not only for the prison itself, but for the Warders' and Pensioner Guards' quarters as well. To assist in the building campaign, a company of Royal Engineers, led by Captain Wray, was sent to Western Australia. These men supervised the convicts in the building of the convict establishment and other public buildings and works throughout the colony.

Work on the prison itself began in 1852 and by 1855 enough of the main cell block, perimeter walls and service buildings were complete for the convicts to be transferred to the site. The prison was completed by 1859. Accommodation and services included the perimeter walls, the Gatehouse, the Main Cell Block, a hospital, workshops and a service building which housed the cook house, bake house and laundry. Six houses were constructed on the western side of the Prison for the senior officers of the establishment. These grand buildings helped confirm the officers' high status in the society of the colony.

By the time transportation ceased in 1868, just over 9,700 convicts had been transported to Western Australia. In 1886, with less than fifty convicts still imprisoned the British government passed control of the Prison to the colonial government and Fremantle Prison then became the Swan River colony’s primary place of incarceration.

The Perth Gaol (built by convicts in the 1850s) was closed and all of its inmates, including the women, were transferred to Fremantle. The original cookhouse, bakehouse and laundry was sectioned off from the rest of the Prison and converted into the colony's only women’s prison. It was extended twice — in the 1890s and in the 1900s. The area continued to serve as the only women's prison in the State until 1970 when a new facility was built on the outskirts of Perth. It was then used as an education facility and assessment centre for new male prisoners.