Le géographe arabe indique également sur sa carte: "Koluvan fait également partie des villes de l'Astlanda. C'est une petite ville ressemblant à une grande forteresse".
En fait, personne ne sait quel fut le plus ancien nom estonien de la ville; peut être Litna ou Lidna (Linn signifie ville en estonien moderne). Le prêtre Henri, dans sa chronique de la Livonie fait référence à Lyndanise en 1219 et 1223, ce qui, en ancien suédois, signifiait "cap en jachère". Les Finlandais, dans leurs chansons traditionnelles connaissaient Kesoniemi (traduction de Lindanäs).
Le nom le plus connu est Reval, venant de l'Allemand et dont la version russe est Ревелъ. Ce nom viendrait de Räväla, la province qui s'étendait alors sur la ville.
Mais le nom actuel de Tallinn a pour origine un fort -une ville- construite par les Danois et appelée Taanilinn (ville danoise) en 1219. Sous domination danoise de 1238 à 1346, l'actuelle Tallinn devient officiellement une ville le 12 Mai 1248 et obtient le droit de frapper sa propre monnaie en 1265. Admise au sein de la Ligue Hanséatique (qui fera l'objet d'un prochain billet) dés 1252, la ville n'en deviendra membre qu'en 1285.
Quant à la légende, elle dit que Tallinn est née sur la colline de Tompea, où Linda aurait amassé de gros rochers sur la tombe de son mari, héros mythique estonien, Kalev. Quant aux larmes de la veuve, elles auraient formé le lac Ülemiste.
On remarque que les noms de Lindanise et Kolõvan sont dérivés des noms de ces héros légendaires.