Around AD71-74 a Legionary Fortress, Eboracum, was built at the junction of the rivers Foss and Ouse. The first fortress defences were probably earth mounds, covered in turf with wooden ramparts. Around AD107-8, these were replaced with stone walls with polygonal bastions and multangular towers. The Vicus (civilian settlement) developed to the southwest of the fortress, on the other side of the River Ouse, which also had defences. By the early third century, Eboracum had become a Colonia, the highest grade of self-governing Roman city.

Some of the City Walls visible today follow the line of the Roman fortress defences. Bootham Bar, for example, was constructed on the site of one of the four gateways to the fortress, the Porta Principalis Dextra. The line of the City Walls running along Nunnery Lane may also follow a defensive Roman line around the Colonia, and the remains of Roman towers and wall can be seen between Monk Bar and Jewbury. A stretch of Roman fortress wall runs parallel to the River Ouse, and can be seen in Museum Gardens.