Aegna, tuolloin tunnettu Wulvesöönä, määrättiin Tallinnaan kuuluvaksi jo vuonna 1265. Kaupunki sai Aegnasta metsän lisäksi myös niittoheinää ja kalaa. Vuonna 1297 Tanskan kuningas Eerik Menved kielsi metsähakkuut Aegnalla, mikä ei kuitenkaan koskenut Tallinnan raatihuonetta. Kertoman mukaan pysyvä asutus syntyi Aegnalle jo 1400-luvun jälkipuoliskolla. Ilmeisesti samaan aikaan rakennettiin myös saaren nykyäänkin suosituin kohde, Eerikneemen kivilabyrintti.
Vuonna 1912 Aegnan asukkaat siirrettiin mantereelle, koska saaresta tuli Pietari Suuren merilinnoituksen meririntaman osa. Rakennustyöt aloitettiin 1914. Pohjoisrantaan rakennettiin 12 tuumainen rannikkopatteristo nro 1, sen luo sotilaiden kasarmi-ruokala (joka on nykyäänkin saaren suurin rakennus), länsirannalle rannikkopatteristo nro 2, luoteisosaan patteriston nro 1 valonheitinsuoja ja pohjoisrannikolle patteristo nro 3.
Alueelle rakennettiin myös kolme kilometriä pitkä kapearaiteinen rautatie. Suurin osa merilinnoituksen rakennuksista tuhottiin I maailmansodassa neuvostoarmeijan perääntyessä. Vapaussodan jälkeen Aegnalla oli Viron suurin merilinnoitusyksikkö, minkä vuoksi saarella avattiin upseerien lapsille alakoulu. Vuonna 1922 länsiosaan rakennettiin upseerien kasino. 1950-luvun lopussa saari avattiin taas kaikille. Vuonna 1961 luotiin virallinen laivayhteys kaupungin kanssa.
