Traces of the first permanent settlement in Aegna date back to the II half of the 15th century. Eerikneeme stone labyrinth, which is now the island’s most visited monument, was probably built at the same time. In 1912 the residents of Aegna were relocated to the mainland, as the island became an important part of Peter the Great’s Naval Fortress. Construction started in 1914. The 12-inch coastal defense battery No. 1, which included the soldiers’ barrack/canteen, was built on the northern coast barrack/canteen (which is still the largest building on the island). Coastal defense battery No. 2 was built on the western coast, the searchlight shelter for the battery No. 1 was built on the northwest coast, and battery No. 3 was built on the northern coast. A narrow-gauge railway (3 km long) was also built.
Most of the buildings were destroyed as the Soviet Army withdrew in the First World War. After the War of Independence, the largest unit of Estonian naval fortress was established on Aegna. Thus, a primary school for the children of officers was opened here. In 1922, a casino was built for the officers in the west corner of the island. At the end of the 1950s, the island was once again opened to the public, and in 1961, an official ship connection was created.