There seems to be a lot of questions regarding how to gain access to the various dungeons and primals within FFXIV: A Realm Reborn. So here is a post explaining how it all fits together.

Most of the dungeons are unlocked via main scenario quests at the level which is the minimum for that dungeon, while others are unlocked via side quests. If a dungeon isn't unlocked then you can not enter it even if others in your party can.

The list below contains the dungeon name, the level requirement, how to unlock and the location of the dungeon.

Dungeon	Level Range	Party Size	Unlocked	Location
Sastasha	15-18	4	Main Scenario	Western La Noscea
Tam-Tara Deepcroft	16-19	4	Main Scenario	Central Shroud
Copperbell Mines	17-20	4	Main Scenario	Western Thanalan
Halatali	20-23	4	NPC Nedrick Ironheart (Vesper Bay, Western Thanalan)	Eastern Thanalan
The Thousand Maws of Totorak	24-26	4	Main Scenario	South Shroud
Haukke Manor	26-29	4	Main Scenario	Central Shroud
Brayflox's Longstop	29-32	4	Main Scenario	Eastern La Noscea
The Sunken Temple of Qarn	32-35	4	NPC Nedrick Ironheart (Vesper Bay, Western Thanalan)	Southern Thanalan
Cutter's Cry	38-41	4	NPC Sibold (Ul'dah Market Ward area)	Central Thanalan
The Stone Vigil	41-43	4	Main Scenario	Coerthas Central Highlands
Dzemael Darkhold	41-44	4	Grand Company quest	Coerthas Central Highlands
Aurum Vale	47-49	4	NPC Nedrick Ironheart (Vesper Bay, Western Thanalan)	Coerthas Central Highlands
Amdapor Keep	47-49	4	After clearing Aurum Vale speak to NPC Nedrick Ironheart (Vesper Bay, Western Thanalan) - He will give a quest leading to a quest given by the Grand Companies for Amdapor Keep.	South Shroud
Castrum Meridianum	49-50	8	Main Scenario	Northern Thanalan
The Praetorium	49-50	8	Main Scenario	Northern Thanalan
The Wanderer's Palace	50	4	NPC Allene (Vesper Bay, Western Thanalan)	Upper La Noscea

After you complete The Praetorium you gain access to the hard versions of the primals:

Primal	Level Range	Party Size	Unlocked	Location
Ifrit	50	8	Quest in Waking Sands After The Praetorium	The Bowl of Embers
Garuda	50	8	Quest in Waking Sands After Ifrit	The Howling Eye
Titan	50	8	Quest in Waking Sands After Garuda	The Naval

Upon beating Titan you can then gain access to The Great Labyrinth of Bahamut.

While on the subject of dungeons we really want to list the dungeon drops on their respective pages so that you know where to look for loot. Compiling the drop lists is challenging however and the SE database may get there first. The dungeon maps also need to be added, the reason they haven't yet is I have yet to reach them on the main scenario. As you know the maps on here are screenshots rather than dat mined. I am trying to strike a balance between updating the site and playing.