Construction of the new walls began under William de Valence, who became lord of Pembroke around 1264. In 1328 Edward III granted Tenby the right to levy dues on merchandise entering the town for the next seven years. This order had two purposes: to help with the construction and maintenance of wall and defences - murage; and of quay - quayage.

The funds raised led to the construction of extra towers in the curtain wall and the outer Barbican tower for the West gate - the present Five Arches.

In 1457 Jasper Tudor's Letters Patent made the Mayor and burgesses of the town fully responsible for the upkeep of the walls and the defence of the town. This led directly to the lower sections of the walls being increased to six feet in thickness, to the walls being considerably heightened, and in many places a parapet walk added.

Outside the landward walls, in what is now South Parade, and St Florence Parade, a dry ditch nearly thirty feet wide was dug for extra protection. In 1588, with the Spanish Armada threatening, the section of wall to the south of the West Gate was rebuilt and strengthened Two large gates led through the walls to the medieval town beyond. The North gate was the largest of these and stood on the site of the present Royal Lion Hotel. It controlled access to the Carmarthen Road. The arch and walls over this entrance had been removed by 1706-7. A later council order, dated 19th June, 1781, stated that 'that part of the gateway' by projecting into the street is a great nuisance and ought to be removed. 'It is hereby unanimously agreed that the said gateway be taken down'. The old West Gate was the present Five Arches.