HMS Leeds Castle (P258) was a Castle-class patrol vessel built by Hall, Russell & Company of Aberdeen, Scotland for the Royal Navy.

The Leeds Castle spent much time performing fishery protection duties around the United Kingdom, as well as being used as a guard ship in the Falkland Islands.

They were a follow-on to the interim Island-class patrol vessel which had been ordered in 1975 when the EEZ was extended to 200 nautical miles (370 km; 230 mi), and as a result of initial experience with the Islands, was considerably longer in order to improve seakeeping in heavy seas, with the extra length giving greater speed from the same power as the Islands and allowing a large helicopter deck to be fitted.

[4][a] Leeds Castle was laid down at Hall, Russell & Company's Aberdeen shipyard as Yard number 985 on 18 October 1979 as the first of two Castle-class patrol vessels.

[4] After commissioning and workup, Leeds Castle, assigned the pennant number P258,[4] started fishery protection patrols around Shetland and in the English Channel in March 1982.

She arrived in the Total Exclusion Zone on 21 May where she was employed as a despatch vessel, duties including acting as a refuelling platform for helicopters transferring stores between the transports Queen Elizabeth 2, Canberra and Norland near South Georgia on 27 May.