A question many have to answer is “Where did my Night Elf grow up?” or “Where were they born?”. Because of their age, this leaves a lot of confusion. The following is a list of Night Elf territories, followed by appropriate eras, plus a blurb about the area if needed.
Destroyed: Zin-Azshari: Formerly known as "Elun'dris" or Eye of Elune before Queen Azshara renamed it in her image. This was the Night Elf capital city, the center of Highborne activity, by the Well of Eternity in the Kaldorei Empire more than 10,000 years ago.
Status Unknown: Hajiri: A city in northwestern Kalimdor prior to the War of the Ancients. Kalo'thera was said to have ascended to the stars there. Maiev Shadowsong was stationed there just prior to the War. It is unknown what happened to the city after the Great Sundering, but it is presumably destroyed.
Hills of Urae: Also simply called "Urae" were a series of plains and hills near the heart of the Kaldorei Empire, bordering Zin-Azshari. It was presumably destroyed during the Great Sundering. 
Galhara: An ancient Night Elven city some distance away, on the opposing side of the Well of Eternity, from Zin-Azshari. The city had hundreds of emerald crystals lining its boundaries. Amongst other things, these crystals in conjunction with each other could defend against magical attacks. It is unknown what happened to the city after the Great Sundering, but it is presumably destroyed.
Lathar'Lazal: The grandest of all Temples of the moon, the name meaning "Seat of the Sky". This temple was constructed by masons, but Queen Azshara personally shaped the waters around it, using the Sharas'dal, Scepter of Tides. She spoke the names of the rivers and seas, and they moved at her command. Creatures of all kinds populated the waters. It was a place of study and amusement for the Highborne of old. It was presumably destroyed during the Great Sundering.
Ruined but still present: Ameth'Aran: Ancient Highborne city. Ruins located in Darkshore.
Bashal'Aran: Ancient Highborne city. Ruins located in Darkshore.
Bathran's Haunt: The site of an ancient night elven ruin, long abandoned by the night elves. Presumably destroyed during the Great Sundering.
Constellas: A sprawling night elven ruin located in Felwood.
Eldre'thar: Ancient Highborne town. Highborne only. Ruins located in Stonetalon.
Ethel Rethor: Ruins located in Desolace.
Falanaar: Night elven town. The site of the first Arcan'dor and now overrun by the Fal'dorei. Ruins located in Suramar.
Faronaar: Night Elven island covered in the ruins of an ancient city. Ruins located in Azsuna.
Isildien: Night Elven city. Ruins located in southern Feralas.
Jaedenar: A series of ancient night elven ruins and two druidic barrow dens on the western edge of Felwood.
Kal'delar: A Kaldorei military city. Ruins located in southwestern Val'sharah.
Kel'theril: Night Elven city. Ruins located in Winterspring.
Llothien: Night Elven city. Located in northeastern Azsuna.
Loreth'Aran: Night Elven city. Home of the Green Dragon Riders. Ruins located in Bloodmyst Isle.
Lornesta: Night elven ruins located in Darkshore, recently unearthed by the Cataclysm wrought by Deathwing.
Mathystra: The ruins of an ancient night elven city before the Great Sundering, but was utterly decimated by the destruction of the Well of Eternity. The ruins contain scattered relics of the old Highborne, and young night elves sometimes attempt to search through the ruins for these relics. Located in Darkshore.
Meredil/Elune'eth: Night Elven and Highborne city. Meredil was once part of Suramar city, but was not protected by the energy shield. Ruins located in central Suramar.
Morlos'Aran: Night elven city. Located on the southern edge of Felwood. Presumably fell during the Great Sundering.
Nar'thalas: Highborne city. Ruins located in the heart of Azsuna.
Ordil'Aran: Night Elven city. Ruins located in Ashenvale, that fell during the Sundering.
Ravenwind: A Highborne city. Ruins located in northwestern Feralas.
Sashj'tar: Night Elven city. This was formerly an ancient elven research community, located in Suramar.
Seradane: Night Elven ruins. A ruined area in the northeastern part of the Hinterlands.
Shala'nir: A Night Elven village. Ruined shortly before the third Demonic Invasion, located in Val'sharah at the base of the world tree Shaladrassil.
Shandaral: Night Elven city. Ruins located in Crystalsong Forest.
Solarsal: Night Elven city. Ruins located in Feralas, on the old Feathermoon Isle.
Stardust: Presumably the ruins of a small night elven settlement or shrine, the Ruins of Stardust (located in Ashenvale) have been overrun by large bog beasts. The most notable feature of the ruin is the stardust shrubs scattered about the area.
Tethris Aran: A night elven city. Ruins located in Desolace, and overrun by wild creatures. The city presumably fell during the Great Sundering.
Zarkhenar: Highborne city. Ruins located in northern Azsuna.
Zoram: Night Elven city. Ruins located in Ashenvale, the Zoram Strand. There is speculation that the ruins at Zoram Strand could be the remnants of Lathar'Lazal, which might explain the heavy naga presence in the area.
Still habitable: Eldre'thalas: Hold home of the Shen'dralar. Highborne only. Barely habitable.
Suramar: An ancient city now overrun by the Nightborne.
Auberdine / Darkshore: Auberdine was a coastal village in Darkshore. Recently it was destroyed in the Cataclysm. Lor'danel now resides up the coast from it, a place for the refugees and survivors.
Ashenvale / Astranaar: Ashenvale is the ancestral homeland of the Night Elves, who remain in control of several holdings throughout the territory. Astranaar is a Night Elven town situation on the east-west road that divides Ashenvale in two.
Moonglade / Nighthaven: A bastion for the druids, both currently and in the past. Nighthaven was/is the center for the Lunar Festival.
Felwood: Unknown towns/settlements. Felwood was where the Skull of Gul'dan resided during the Third War. This was used by the demons to utterly corrupt the land, making it impossible to live in. Recently, attempts have been made to heal the land and purge the demons.
Winterspring / Starfall Village: An out of the way village up in snowy Winterspring. Presides over a barrow den for sleeping druids.
Azshara / Nendis: Azshara was a coastal area, though a Satyr threat was present there was a small town called Nendis on the shore. When the Naga first appeared 10 years ago they wiped out the city in an attempt to aid Illidan's escape.
Feralas / Dire Maul: Feralas was discovered only in the last few years, according to two in-game lore sources. The Highborne, however, have been in the area for 10,000 years. Currently, Feathermoon Stronghold has been rebuilt here after it was destroyed by the Cataclysm. Sentinels train here and Shandris Feathermoon leads the army from this position.
Desolace / Nigel's Point: Because Feralas had not been discovered until recently, the same is likely true of Desolace. The outpost of Nigel's Point is sparse and has a heavy human population.
The Barrens, Durotar, etc: There is no evidence that the Night Elves built any post-sundering settlements in these areas.
The hills of Hyjal: A generic term for anywhere on the slopes of the mountain, from the actual Hyjal zone to Ashenvale, to what is now Felwood.
Teldrassil / Darnassus: Teldrassil is less than 10 years old. Those who are born on it would be that young or younger. This is the Night Elven capital city now, housing the Temple of Elune.
Val'sharah/Lorlathil: Val'sharah is located in the Broken Isles. The forests of Val'sharah predate the War of the Ancients, but has been maintained into modern times. It was in the Night Elven village of Lorlathil that the Stormrage twins were born and, in the wilds surrounding, where druidism first began.