The medieval structure, which was located at the northwest corner of St Giles' Cathedral and was attached to the west end of the Luckenbooths on the High Street in the Old Town, was first established in the 14th century by royal charter.

Over the years it served a variety of purposes such as housing the Burgh Council, early meetings of the Parliament of Scotland and the Court of Session.

The charter, written in Latin, was endorsed "Carta fundi de la Belhous" (English: Charter of the site of the Belhous), signifying the purpose of the site for a new Belhouse, successor to the earlier pretorium, and may be translated: Know ye, that we have given, granted, and by this our present charter have confirmed, to our beloved and faithful, the Burgesses and Community of Edinburgh, and their successors in time to come, 60 feet in length and 30 feet in breadth of land lying in the market place of the said burgh, on the north side of the street thereof; giving and granting to them, and their foresaid successors, our special license to construct and erect houses and buildings on the foresaid land, for the ornament of the said burgh, and for their necessary use.There is no record of construction on the site but, on 3 October 1403, the earliest burgh record mentions the "Pretorio burgi" – the Pretorium of Edinburgh – for the first time.

The bellhouse (or belhous) often had a steeple or tower that contained a civic bell, the ringing of which was used to regulate the business and civil matters of the burgh.

In 1811 the council moved across the street to the north range of the Royal Exchange building which was termed the City Chambers rather than the Tolbooth.

From 1785 executions, which previously had taken place at the Mercat Cross or the Grassmarket, were carried out on the roof of a two-storey extension on the west side of the Old Tolbooth which provided a platform equipped with a gallows so that the public could view hangings.

The heads of the most notorious were placed on "the prick of the highest stone": a spike on the Old Tolbooth's northern gable facing the High Street.

[10] Edinburgh's foremost 18th century historian, Hugo Arnot, wrote the following detailed description of the prison to expose the shocking conditions within.

This is the more inexcusable, since, by making a drain to the north, over a very narrow street, such a declivity might be reached, that, with the help of water, of which there is command, the sewer might be kept perfectly clean.

But, wherever we found the prisoners confined to one apartment, whether on account of their delinquencies, or that they were unable to pay for a little freedom, the rooms were destitute of all accommodation, and very nasty.

In the second, which is called the iron room, which is destined for those who have received sentence of death, there were three boys: one of them might have been about fourteen, the others about twelve years of age.

The straw had been originally put into the room for them to lie upon, but had been suffered to remain till, worn by successive convicts, it was chopped into bits of two inches long.

But there we had no leisure for observation; for, no sooner was the door opened, than such an insufferable stench assailed us, from the stagnant and putrid air of the room, as, notwithstanding our precautions, utterly to overpower us.