When the Roman "Governor of Britain" Agricola advanced North in AD79 and reached the mouth of the River Esk at what is now Inveresk, he encountered the Celtic tribe of Votadinii.
The Votadinii controled the Forth River valley and based themselves at Dunedin. . . what is now probably Edinburgh Castle. There is plenty of archaelogical evidence that the Roman army mixed on a day to day basis with the locals. After all most of the Roman army was made up of Celts (Gauls) from mainland Europe. Although they fought, and defeated the Pictish leader Calgacus at Mons Graupius in AD84, the Romans could never master Caledonia and by 211 had retreated behind Hadrians wall, about a hundred miles to the south. By 410 they had left Britain for good. The first United Scotland

By the sixth century four Kingdoms had developed in what is now Scotland;
To the North, the Picts,
To the far West, the Scots
To the West, the Britons
To the South-East, the Angles. For the next two of hundred years these four kingdoms struggled, beset by Viking raiding parties , until in the 9th century the King of Dalraida, Kenneth MacAlpin, fought his way to something like a united Scotland. His Grandson, Duncan I, became the first King of Scotland in 1035
Medieval and Renaissance Edinburgh
Although at this time Scottish rulers tended to base themselves further north across the Forth, King Malcolm III Canmore (died 1093) built his castle at Edinburgh, and his wife Queen (Saint) Margaret built a chapel within its walls - now the oldest building in the city. Her son, David I built the Abbey at Holyrood, a mile to the East along "The Royal Mile". Castle and Abbey became the anchor points of Edinburgh; a thriving town grew up along side the road between them, connected to Lieth, Edinburgh's port and trade-link to the world. (see map below)
During the Wars of Independence Edinburgh Castle was captured by the English until Robert the Bruce's nephew, Thomas Randolph daringly recapture it by climbing its steep and craggy sides in the dead of night. Robert the Bruce granted Edinburgh a Royal Charter in 1329. If Edinburgh did not grow outwards at this time, it did grow upwards. By the end of the 1500's it was established as the Capital of Scotland, and growing in population the inhabitants chose to build high houses close to the protection of the Castle: high tenement buildings most of which can be seen to this day.