Hr.Ms. Middelburg (M858) was een mijnenjager van de Alkmaarklasse en droeg de naam van de Zeeuwse hoofdstad Middelburg, een stad met een lange geschiedenis in handel, scheepvaart en maritieme verdediging.
De kiel van de Middelburg werd gelegd op 11 juli 1983 bij Van der Giessenāde Noord in Alblasserdam. 22 november 1986 volgde de tewaterlating, waarna het schip werd afgebouwd. Op 10 december 1986 trad de Middelburg officieel in dienst bij de Nederlandse marine.
Tijdens haar inzet opereerde Middelburg in Nederlandse wateren en binnen NAVOāverband. Het schip werd gebruikt voor het opsporen, classificeren en neutraliseren van zeemijnen, waarbij de stille romp en de geavanceerde sonarinstallaties essentieel waren.
De Middelburg werd in 2011 na bijna dertig jaar dienst bij de Nederlandse marine buiten dienst gesteld. In 2022 werd de Middelburg samen met zusterschip Haarlem verkocht aan Pakistan.