Finnish tribes are believed to have settled on the southern coast of the Gulf of Finland as far back as 2000 BC. At the end of the first millennium, in the suburbs called Iru, there used to be a castle with a settlement nearby. However, evidence of Tallinn's existence comes from 1154, when Arab cartographer al-Idrisi included it on his world map. The city was also known as an important trade port between Scandinavia and Russia.

In the late 12th Century, the Baltic Crusades began against the pagans on the Baltic shores by the Christian kings of Sweden and Denmark, and the Teutonic Knights. Christianity was forcibly imposed on the locals. In 1219, the Danes took control of Tallinn. In 1285, the city became a member of the Hanseatic League, a military and trade alliance of German cities. The Danes sold Tallinn to the Teutonic military order in 1345.

In medieval times, Tallinn’s 8,000 inhabitants enjoyed a strategic location on a major trade route between Northern and Western Europe, and Russia. It was heavily fortified with 66 turrets and city walls. German influence became stronger with the beginning of the Protestant Reformation. However, in 1561 Tallinn came under the political authority of Sweden, as a Swedish dominion, a term used to describe territories under Swedish rule that were not fully integrated with Sweden.

Between 1549 and 1625, St Olav’s Church in Tallinn was the tallest building in the world, with a 159-m Gothic spire built so as to see the merchant city from sea. In 1625, the spire was hit by lightning, but was later rebuilt.