St Paul's Gate was built by the Knights of St John in the second half of the 15th century to control movement between the two harbours of Rhodes, the Mandraki and the Commercial Harbour and the Mole of St Nicholas. A polygonal bulwark surrounds the tall central tower.
The coats-of-arms of Pope Sixtus IV and Grand Master d'Aubusson incorporated above it and below the marble plaque with its relief of St Paul indicate that the tower could be dated to 1476-84. However the arrangement of the fortification would seem to date it from an earlier period, perhaps from the rule of Grand Master Zacosta (1461-67). Pierre d'Aubusson may well have repaired the gate c.1477, when he reinforced the north wall of the city.