27 березня 1996 року було завершено прийом об’єктів Кримської військово-морської бази і урочисто піднято Військово-Морські Прапори України на 17 кораблях і суднах створеного  Південного військово-морського району ВМС України в Новоозерному. До складу ВМС увійшли  великий десантний корабель „Костянтин Ольшанський”,  десантні кораблі на повітряній подушці „Горлівка”, „Краматорськ”, „Артемівськ”, малі протичовнові кораблі „Хмельницький” і „Ужгород”, базові тральщики „Мелітополь”, „Маріуполь”  й „Генічеськ”, розвідувальні кораблі „Івано-Франківськ” і „Чернівці”, рейдовий буксир „Ковель”, протипожежний катер „Євпаторія”,  плавкран „Каланчак”  та інші судна  забезпечення. Кораблі та катери передавалися у занедбаному та розграбованому стані, російські військовослужбовці навмисно псували матеріальну частину, викрадали і нищили технічну документацію.  Завдяки роботі особового складу та шефській допомозі регіонів України, більша частина корабельного складу була відновлена.