The earliest written record of a formal connection between Rome and Scotland is the attendance of the "King of Orkney" who was one of 11 British kings who submitted to the emperor Claudius at Colchester in CE 43 following the invasion of southern Britain three months earlier. The apparently cordial beginnings recorded in Colchester did not last. We know nothing of the foreign policies of the senior leaders in mainland Scotland in the 1st century, but by CE 71 the Roman governor Quintus Petillius Cerialis had launched an invasion.

The Votadini, who occupied the south-east of Scotland, came under Roman sway at an early stage and Cerialis sent one division north through their territory to the shores of the Firth of Forth. The Legio XX Valeria Victrix took a western route through Annandale in an attempt to encircle and isolate the Selgovae who occupied the central Southern Uplands. Early success tempted Cerialis further north and he began constructing a line of Glenblocker forts to the north and west of the Gask Ridge which marked a frontier between the Venicones to the south and the Caledonians to the north.

In the summer of CE 78 Gnaeus Julius Agricola arrived in Britain to take up his appointment as the new governor. Two years later his legions constructed a substantial fort at Trimontium near Melrose. Agricola is said to have pushed his armies to the estuary of the "River Taus" (usually assumed to be the River Tay) and established forts there, including a legionary fortress at Inchtuthil.

The total size of the Roman garrison in Scotland during the Flavian period of occupation is thought to have been some 25,000 troops, requiring 16–19,000 tons of grain per annum.