24 квітня 2000 року російська протикорабельна ракета П-35 “Прогрес”, випущена з берегової установки на мисі Херсонес, влучила в український теплохід “Павло Верещагін”.  Цей інцидент став важливим сигналом, що росія вже тоді тестувала реакцію України на свої військові дії, перевіряючи, чи можна безкарно атакувати українські судна в міжнародних водах.

Ракетні навчання росії проходили на мисі Херсонес, де росіяни розгорнули цілий ескорт з 13 кораблів і суден Чорноморського флоту. Вони охороняли район стрільб, однак український корабель, який прямував зі Стамбула до Скадовська, потрапив у зону ураження, не викликавши жодних підозр. 

Ракета, що мала холосту боєголовку, влучила в корпус судна, пройшовши через рубку, що спричинило величезні руйнування. Внаслідок удару утворився отвір діаметром 2 метри на вході та 4 метри на виході. Постраждав 37-річний електромеханік Вадим Пономаренко.

Командування Чорноморського флоту росії висунуло звинувачення на адресу капітана українського судна, але експерти вказали на неналежну організацію охорони району навчань. Кораблі, що мали забезпечувати безпеку, повинні були бути розміщені на такій відстані, щоб їх радарні зони спостереження перекривалися, що дозволяло б вчасно виявити будь-яке судно, яке потрапляє в небезпечну зону.

Розслідування показало, що капітан не отримав жодного повідомлення від Центру навігаційної інформації України в Одесі, що ставить під сумнів версію російської сторони. Позиція російського командування, що відмовилося розглядати претензії, лише підкреслює агресивну політику росії та її перших спроб нападу на Україну.

Цей інцидент став першим свідченням того, що росія ще у 2000 році розглядала можливість застосування сили щодо України. Ця подія стала однією з перших провокацій, що вказували на подальше загострення відносин і на наміри росії порушити норми міжнародного права та територіальну цілісність України.