The Tallinn City Archives were established with the documents of the City Council. The Council Archives – a collection of documents that for a long time possessed legal value – apparently began to be collected during the first half of the 13th century. The earliest surviving lists of documents located in the Town Hall date from the middle of the 17th century, and a floor plan of the Town Hall Archives has also survived from that time. The organization, scientific study and publication of archival materials as historical documents was begun in the 1840s by Friedrich Georg von Bunge, Tallinn City Council magistrate and former professor of the University of Tartu.
The City Archives as an institution opened on October 13, 1883 (October 1, 1883 according to the Old Style). On that day the municipal government employed the first regular city archivist, Theodor Schiemann. In 1877, the City Archives took charge of all Tallinn City Council documents and those of its subsidiaries that had lost their function due to municipal reform. In 1896, Schiemann’s successor, Gotthard von Hansen, published a catalogue of the older part of the City Council Archives (Gotthard v. Hansen, Katalog des Revaler Stadtarchivs, Reval 1896). In 1924–1926 Otto Greiffenhagen published the revised edition of this catalogue – Gotthard von Hansen, Otto Greiffenhagen, Tallinna linna arhiiwi kataloog/Katalog des Revaler Stadtarchivs.

For a long time the City Archives consisted only of the City Council Archives, but from the 1920s, they started to accept documents from Tallinn Municipal Government (which had replaced the former City Council) and its subsidiaries, city enterprises and the former guilds of Tallinn.

During the second half of the 1920s, the Tallinn City Archives became one of the most important centres for historical research in Estonia. A great contribution to this was made by Paul Johansen – a historian of danish descent born in Tallinn. After graduating from the University of Leipzig, he became assistant to the City Archivist in 1924 and was City Archivist from 1934–1939. From 1923–1939, a total of nine publications based on City Archives source materials appeared. Since 1933, the Tallinn Historical Society was based at the Archives, and until 1937 the City Archives also functioned as the City Museum. The offices and depositories for archival materials were located in the Town Hall until 1937, when the City Archives acquired its own building – at Rüütli 8/10.

During the first Soviet occupation in 1940, Tallinn City Archives were reorganized and renamed Tallinn City and Harju County Archives.
In the period 1940–1998 the name and status of the archives were changed repeatedly:
1941–1944: Tallinn City Archives;
1945–1950: Tallinn City and Harju County State Archives;
1950–1963: Tallinn City and Harju Region State Archives;
1963–1975: the State Archives of the City of Tallinn;
1975–1989: Tallinn Central State Archives of the Estonian SSR;
and from 1989: Tallinn City Archives (until November 1994 with the status of state central archives).
From November 1994 until 1998 Tallinn City Archives were subordinated to the City Office as a municipal institution.
In accordance with the Archives Act passed in 1998, the City Archives were reorganized into a city administrative agency in 1999.

As a result of a Soviet bombing raid between 9–10 March 1944, the Archives building on Rüütli Street was destroyed, together with a great number of newer archive materials. The older part of the Archives, the City Council Archives, had been evacuated and remained untouched in the raid. In the summer and autumn of 1944, part of the City Council Archives and other older archive materialswere sent to Germany by order of the German occupying authorities. These records were returned to the City Archives in October 1990.

In 1940 the acquisition of documents from institutions liquidated by the Soviet authorities began. This continued during the post-war years. From the 1960s onwards, documents were also acquired from operating institutions.
In the period between 1947 and 1973, the Archives were located at Lai 40. They then moved to the building at Tolli 8. during the second half of the 1980s, the neighbouring buildings at Tolli 6 and Tolli 4 were also restored for use by the Archives. These have been in use since the summer of 1989.

After the restoration of the Republic of Estonia in 1991, the collections of the City Archives began to grow rapidly. This process was especially intense during the second half of the 1990s, when a great number of archives were acquired from liquidated or reorganised institutions of the Soviet period. In connection with the reforms instituted in Estonia during the 1990s, the practical purpose of the records concerning property rights and employment has grown.