The Domesday Book, 1086, records that half of York was owned by the King and the other half by influential Normans. During this time, the rebuilding of the Minster began.

In 1089, William II laid the foundation stone of a church and a new abbey, dedicated to St Mary, which would become one of the ten richest abbeys in England during the medieval period.

The City Walls were rebuilt in stone in the period from the mid- 13th to the early-14th century. The four main gateways into the city (Bootham Bar, Monk Bar, Micklegate Bar and Walmgate Bar) were rebuilt with great elaboration and included barbicans. One of two motte and bailey castle was also re-built in stone at this time which included Clifford's Tower. There is a gap in the city walls around the Clifford's Tower area between the 19th century Tower 1 and Fishergate Postern mainly because the castle and its wet moats provided sufficient protection, while a chain across the River Ouse restricted access by boat into the town.

During the 15th century, the population of York went into decline as a result of the shifting of the important wool industry and the Wars of the Roses (1453-1487). In 1536, Henry VIII began the Dissolution of the Monasteries. York, as a major religious centre, suffered greatly, but the first surviving account of the walls, by John Leland, dates from around this time.