Desde el final del bulevar Mere en Tallin, Linnahall se presenta como una masa larga y baja de piedra caliza y hormigón dispuesta entre el Casco Antiguo y la bahía, mantenida deliberadamente por debajo de la silueta medieval para que las agujas sigan siendo visibles desde el agua. Amplias escalinatas suben por sus flancos hasta una cubierta pavimentada como plaza pública, desde donde una secuencia de terrazas desciende hacia un pequeño muelle, un helipuerto y las aguas abiertas del golfo de Finlandia. Bajo esa superficie se encuentran un anfiteatro para 4.200 personas, un vestíbulo de 6.000 metros cuadrados, una pista de hielo, cafeterías, una bolera y un estudio de grabación.
El edificio se inauguró en el verano de 1980 como el Palacio de Cultura y Deportes V. I. Lenin, a tiempo para la regata de vela de los Juegos Olímpicos de Moscú, de la cual Tallin fue sede en representación de una capital sin costa. Fue uno de los más de 120 proyectos planificados bajo el programa olímpico de la ciudad, junto con el centro de vela en Pirita, la torre de televisión, el Hotel Olümpia y una nueva terminal de aeropuerto.
