Антонов-Овсеенко выехал в Крым. Фронт к этому времени проходил близ станции Ак-Монай, восточнее деревни Дальние Ключи на Керченском полустрове. Дыбенко встретил командующего в Джанкое, где находился его штаб. Доложил, что приступил к формированию Крымской Красной Армии, насчитывающей уже 13 тысяч штыков и сабель (в 1-й Заднепровской дивизии было 4500). Вместе побывали в Симферополе и Севастополе. Антонов-Овсеенко спешил в Донбасс. Дыбенко заверил его, что в течение ближайших нескольких дней Крымская Красная Армия овладеет укрепленными позициями белых, нанеся удар через Керченский пролив и Таманский полуостров, выйдет в тыл Деникина и поможет армиям Южного фронта разгромить противника на Ростовском и Таганрогском направлениях. Командующий внимательно выслушал Дыбенко и, по существу, одобрил его план. Директива повернуть части Крымской Армии на Донбасс отдана не была. Позднее Дыбенко узнал, что в мае 1919 года ЦК РКП(б) объявил выговоры Наркомвоенмору Украины Н. И. Подвойскому, командующему Украинским фронтом В. А. Антонову-Овсеенко за задержку переброски войск в Донбасс и потребовал ст руководящих работников Украины принять меры для освобождения Донецкого бассейна от белогвардейцев… В своих мемуарах Антонов-Овсеенко писал, что его увлекла фантастическая мечта прорваться в Керчь и оттуда создать угрозу тылам «добровольческой армии» Деникина.
6 мая 1919 года была образована Крымская советская республика. Павел Ефимович — народный комиссар по военным и морским делам и командующий Крымской Красной Армией. А. М. Коллонтай— начальник политического управления армии. Несколько позднее заместителем наркомвоенмора стал двадцатидвухлетний Иван Федорович Федько. Его приезд в Крым очень обрадовал Павла Ефимовича.
— Явился в ваше распоряжение от товарища Ленина, — по военному четко доложил молодой подтянутый командир и подал документы. Федько рассказал о себе.
Военную службу он начал в Феодосии в годы империалистической войны прапорщиком. Здесь же в 1917 году вступил в партию большевиков. Формировал отряды Красной гвардии, сражался с немецкими оккупантами. Командовал красными частями на Северном Кавказе. В Астрахани встретился с С. М. Кировым.
— Вот он-то и послал в Москву к товарищу Ленину, — говорил Федько. — А Владимир Ильич направил меня, как знающего Крым и Украину, уже к вам. И вот я здесь.
— Прибыли как нельзя кстати, — с радостью произнес Дыбенко. — У нас неспокойно…
9 мая 1919 года поднял мятеж бывший гетмановский атаман и петлюровский офицер Григорьев, командовавший тогда 6-й дивизией Украинского фронта. В выпущенном «универсале» он обещал «свободу торговли», «защиту собственности», «свободные при участии всех партий (кроме большевиков) советы» и многое другое. Такие посулы вполне устраивали зажиточные слои населения. Восстание охватило значительную часть Южной Украины. Под угрозой оказались Николаев, Херсон, Одесса, Харьков. 11 мая григорьевцы захватили Екатеринослав и Кременчуг. Еще через день они дошли до Золотоноши и открыли путь на Киев.
Основная тяжесть ликвидации григорьевщины легла на войска, сосредоточенные в Харьковском военном округе, и добровольческие рабочие отряды, которыми командовал А. Я. Пархоменко. Активное участие принял в ликвидации мятежа и Дыбенко. Он командовал советскими войсками, действовавшими в районе от Александровска до Екатеринослава. В течение двух недель с мятежом было покончено…
Дыбенко возвратился в Крым. Нужно было готовить армию к новым боям. На каждом шагу приходилось встречаться с большими трудностями. Не хватало командиров. Мало было коммунистов в войсках и особенно в гражданских учреждениях. Забот по горло. Как-то Павел Ефимович показал Коллонтай письмо от Семашко: наркомздрав писал, что скоро Крым превратится во всенародную здравницу, настоятельно просил надежно охранять дворцы, где будут отдыхать трудящиеся.
— Прекрасно, Павел! — радовалась Александра Михайловна.
— И я так думаю. Только ведь сейчас заботы совсем другие. Красноармейцев заели вши. Войска разуты и раздеты. Мастерские, которые мы открыли в Симферополе и Севастополе, стоят — нет материалов. А чем вооружать нашу новую армию?
— Да, нелегко нам, Павел.
До предела была загружена работой и Коллонтай в политическом управлении армии. Открыли школу политсостава, проводили беседы с бойцами, среди населения, издавали журнал, газету, писала позднее Александра Михайловна, вспоминая о «крымском периоде».
Но слишком коротким был тот «крымский период». Белые находились рядом. Вдоль побережья непрерывно курсировали корабли интервентов. И военачальники, и гражданские руководители Крыма понимали, что враги готовятся к наступлению…
И оно скоро началось… Деникинцы прорвали фронт в Донбассе и часть сил перебросили на Чонгарский и Перекопский перешейки, намереваясь отрезать Крымскую Красную Армию, а затем уничтожить ее. Военная и политическая обстановка обострилась. 16 июня 1919 года в Симферополе состоялось чрезвычайное совещание членов правительства республики и армейских работников. С докладом выступал П. Е. Дыбенко.