Судно построено в 2000 году на Хабаровском судостроительном заводе имени 60-летия СССР. С 5 ноября2000 года входит в состав морского дивизиона кораблей Сахалинского морского отдела Дальневосточного таможенного управления ФТС России. Строевой (заводской) номер — 421.
В ноябре 2000 года — БТС «Павел Верещагин» отправился из Хабаровска во Владивосток в свой первый поход для проведения ходовых испытаний в заливе Петра Великого и доводки основных механизмов. Экипаж под руководством капитана корабля Геннадия Юдина освоил все тонкости нового судна на воздушной каверне. Пунктом базирования судна временно был выбран порт Корсаков на юге Сахалина[3].
17 мая2004 года — БТС «Павел Верещагин» при проведении специальной морской операции с привлечением сил СОБРа Сахалинской таможни в российских территориальных водах Приморского края задержал рыболовный сейнер «Взморье», который вёл браконьерский промысел краба. На борту сейнера таможенники обнаружили более тонны живого краба. Судно было отконвоировано в порт Невельск для проведения дальнейшего разбирательства. Краб выпущен в море.
19 мая2004 года — БТС «Павел Верещагин» ночью задержал рыболовную шхуну «Мали», шедшую под флагом Белиза. Шхуна пыталась уйти от таможенников, маневрировала, команда начала сбрасывать улов за борт. Однако ввиду высокой скорости «Павла Верещагина» (50 узлов) шхуну удалось догнать. Досмотровая группа, высадившаяся с лодки на борт, проверив рыбаков, не обнаружила не только разрешения на промысел, но и документов на саму шхуну. Судно-нарушитель было отконвоировано в порт Находка и передано пограничникам для дальнейшего разбирательства[4].
25 августа2004 года — БТС «Павел Верещагин» в районе Владивостока задержал два браконьерских судна: траулеры «Колымский» (порт приписки Холмск) и «Мирный» (порт приписки Невельск), незаконно проводившие лов краба. При досмотре на борту траулера «Колымский» было обнаружено более 2,7 тысяч крабов, на траулере «Мирный» — более 9,5 тысяч. Живой краб выпущен в море. Суда-нарушители под конвоем были сопровождены в порт Владивосток для проведения дальнейшего разбирательства[5].
3 ноября2005 года — БТС «Павел Верещагин» в районе мыса Золотой было задержано судно-контрабандист «Альтаил», шедшее под Камбоджийским флагом. При проверке выяснилось, что на борту судна находится около 10 тонн краба разных видов. Разрешения на промысел у капитана не было. Кроме того, «Альтаил» находился в российских территориальных водах в режиме «закрытой границы», что также является незаконным. Краб выпущен в море, а судно отконвоировано в порт Невельск для проведения расследования[6].
20 апреля2007 года — БТС «Павел Верещагин» успешно прошёл очередную проверку готовности к навигации. Были опробованы на различных режимах новые системы акустики и навигации, проведено условное задержание контрабандистов, испытания за живучесть судна (пожар в машинном отсеке и пробоина в радиорубке). Члены команды, действуя слаженно, в нормативные сроки устранили все нештатные ситуации[7].
4 сентября2007 года — БТС «Павел Верещагин» в водах Татарского пролива в очередной раз столкнулся с рыболовной шхуной «Альтаил» под Камбоджийским флагом. Судно было остановлено принудительно, после проведения предупредительных выстрелов. На борту судна-нарушителя таможенники обнаружили более 17 тонн краба: 4,2 т. камчатского, 10,7 т. синего, и 2,3 т. стригуна-опилио. По факту нарушений вынесено определение об административном правонарушении, судно-нарушитель отконвоировано в порт Корсаков[8].
20 июня2011 года — БТС «Павел Верещагин» в ходе специальной морской операции был зафиксирован незаконный выход российского судна за пределы территориального моря РФ с грузом морепродукции на борту при попытке схождения с другим транспортным судном, прибывшим со стороны сопредельного государства, для осуществления перегруза добытой морепродукции. Увидев таможенное судно, капитан шхуны взял курс в российские воды, попутно выбрасывая за борт находившиеся на судне водные биологические ресурсы. Однако полностью избавиться от признаков противоправной деятельности не успел. Когда в результате непродолжительного преследования досмотровая группа высадилась на борт, там еще оставалось 180 кг живого краба, 30 кг свежемороженого осьминога и полторы тонны сельди. По результатам проведенного досмотра судна возбуждено дело об административном правонарушении[9].
25 апреля2012 года — БТС «Павел Верещагин», вместе с другим БТС Сахалинского отдела «Виталий Кирсанов», провели проверку боевой готовности в водах Татарского пролива. Задачи, поставленные перед составами обоих судов, заключались в отработке действий при захвате судна-нарушителя, спасении утопающего, стрельбе, пожаре на борту и затоплении. Результаты учений очередной раз подтвердили высокий уровень экипажей и техническую готовность корабля, и его оснащения[10].
5 декабря2014 года — БТС «Павел Верещагин» задержал судно, незаконно перевозившее груз крабов. На борту обнаружили более восьми тонн живого краба. Судно было арестовано и доставлено в Невельский порт[11].
Россия
ФТС России