«Горлівка» (заводський № 2041) був збудований в Угорщині, м. Будапешт, на судоверфі «Ангіалфолді Гіарегісег» у 1965 році і зарахований в списки кораблів ВМФ СРСР у 1965 році. 10 січня 1996 року транспорт «Мезень» був переданий Україні.
14 липня 1997 року, згідно з українсько-російською угодою про параметри розподілу Чорноморського флоту розпочався процес передачі корабля ВМС України.В склад Військово-Морських сил України корабель увійшов 10 серпня 1997 року, де отримав назву «Кривий Ріг» і бортовий номер U753. Після був перейменований та отримав назву «Горлівка».
До квітня 2014 року базувався у Новоозерному в бухті на озері Донузлав.
В кінці березня 2014 року на судні був зірваний прапор ВМС України та піднятий прапор ВМФ Росії.
19 квітня 2014 року судно було повернуто Україні та перебазоване в Очаків.