До Харькова Павел добрался благополучно, никто к нему не придрался. Он уже знал, что брат Федор служит у петлюровцев. Хотел встретиться с ним, «вправить мозги и наставить на верный курс». Только вот адреса не знал, да и подпольщики ничего не слыхали о Федоре… В Харькове на немецкий патруль наткнулся, но обошлось: одежда мастерового и паспорт не вызвали подозрений. Однако решил убраться из города. Отправился дальше. Думал задержаться в Симферополе, но и здесь на каждом шагу патрули. Поехал в Севастополь, где предстояло обосноваться. Явок, полученных в штабе Антонова, было несколько. Разыскал на Корабельной стороне «родственников», бывшего матроса, ныне сторожа городского офицерского яхт-клуба, у него и обосновался.
Несколько дней никуда не выходил, привыкал к обстановке. Из садика матроса хорошо просматривалась бухта и сам город… Красив Севастополь! Маленькие уютные домики, раскинувшиеся по высоким берегам бухты, утопают в зелени. Сверкает на солнце море, и вовсе оно не черное, даже не голубое, а зеленовато-синее, а то желто-зеленое… Привыкал к нелегальному положению, к своей новой фамилии. Друзья помогли устроиться грузчиком на товарную станцию. Весьма пригодилась специальность, приобретенная в Рижском порту! И подрядная работа устраивала, выполнил что положено, получил деньги и свободен.
Установить связи с судостроителями, рыбаками Балаклавы, рабочими порта, моряками вспомогательного флота помогли подпольщики. В Севастополе не так уж мало трудового люда; только на морзаводе 3,5 тысячи, а всего на предприятиях Севастопольского военного порта более 7 тысяч. Есть где развернуться.
Ряды подпольщиков росли, накапливались силы. Труднее налаживались контакты с боевыми кораблями. Дыбенко жалел, что нет в Севастополе Н. А. Пожарова, он был направлен сюда Центральным Комитетом партии с заданием превратить Севастополь в «Кронштадт юга». Николай Арсеньевич быстро вошел в доверие, его избрали секретарем городского комитета партии. 26 октября 1917 года, получив известие о победе революции в Петрограде, взяли власть в свои руки севастопольцы. Пожаров стал председателем Совета. В Смольный послали телеграмму: «Приветствуем победную революцию. Власть Советом взята. Ждем распоряжений. Севастополь».
Дальнейшее Дыбенко было известно. Весной 1918 года войска кайзеровской Германии нарушили условия Брестского мирного договора, оккупировали значительную часть западных областей страны, в том числе и Крымский полуостров, установили жестокий военный режим. Трудящиеся Таврии под руководством ушедших в подполье партийных организаций поднялись на борьбу с врагами…
«Как проникнуть на боевые корабли?» — уже в который раз спрашивал подпольщиков Дыбенко. Его волновала судьба Черноморского флота… Еще 27 марта 1918 года Советское правительство потребовало от исполняющего обязанности командующего контр-адмирала Саблина перебазировать корабли из Севастополя в Новороссийск. Реакционное офицерство вывело не весь флот… Совет Народных Комиссаров принял решение: чтобы враг не воспользовался боевыми судами, затопить их в Новороссийской бухте. Директиву В. И. Ленина об уничтожении флота привез Иван Вахрамеев. Он, Николай Пожаров, Николай Глебов-Авилов и другие большевики, прибывшие из столицы, долго и терпеливо разговаривали с офицерами и меньшевистско-националистическими элементами экипажей, требовали выполнить директиву. И все же затопить удалось не все боевые суда, часть вернулась в Севастополь. «Вот они стоят, красавцы», — Дыбенко смотрел на рейд. Подпольщики спрашивали: «Неужели эти богатыри немцам достанутся?» — «Может и это случиться. Такую участь готовили господа офицеры Балтийскому флоту, но на их коварном пути встали революционные матросы. Героический Ледовый поход перекрестил замыслы врагов. Черноморские корабли надо уничтожить!!!» Своими мыслями поделился с подпольщиками.
Стали вместе думать, искать выход…
Ближе к осени подпольщики Крыма и всей Северное Таврии готовили вооруженные выступления, сил к тому времени набралось достаточно. Уже действовали боевые группы и на некоторых боевых судах, в том числе и на линейном корабле «Воля».
И вдруг стряслась беда. Близ дома, где жил Дыбенко, появился подозрительный тип, ходит, высматривает. За улицей установили наблюдение, подпольщики по очереди дежурили, «подозрительный» словно в воду канул.
Немного успокоившись, Дыбенко отправился в город. «Не могу я прятаться, не для того меня послали». Ночью возвращался с конспиративного совещания. (Проходило оно в бухте Голландия, в штольне.) Заметил, будто кто-то прячется в кустах. «Хвост», — подумал Павел, продолжая идти. Убедившись, что поблизости никого нет, перемахнул через невысокую изгородь, прижался к земле. «Хвост» прошел совсем близко, шаги удалились и пропали. Дыбенко вылез из укрытия, пробрался на «запасную квартиру», провел остаток ночи в маленьком сарайчике, заполненном дровами и садовым инвентарем.