Большевики решили использовать популярность Котовского в Бессарабии, которую после взятия Одессы Красная армия собиралась освобождать, чтобы затем сокрушить «боярскую» Румынию и прийти на помощь красной Венгрии. 13 апреля 1919 года он с благословения секретаря Одесского губкома партии Яна Гамарника получил мандат, где говорилось: «Тов. Котовскому Григорию Ивановичу, как испытанному и боевому товарищу, поручается организация боевых частей для освобождения Бессарабии от гнета мирового империализма. Тов. Котовский работает на территории Одесского округа и подпольно в Бессарабии. Все советские учреждения, исполкомы, ревкомы, также подпольные советские организации оказывают указанному товарищу безусловное содействие». Тогда же, 20 апреля, Котовский получил первую официальную советскую должность — военкома пограничного с Бессарабией Овидиопольского военного комиссариата. Ему предложили создать группу для подпольной работы в Бессарабии. Котовский собирался высадить отряд партизан на другом берегу Днестра, использовав для этого рыбацкие лодки. Но румыны узнали о плане десанта. Из Аккермана в Овидиополь пришел румынский монитор и расстрелял все собранные для десанта лодки.
В короткий срок Котовскому удалось завербовать более трех тысяч добровольцев, в том числе немало своих соратников из числа одесских и бессарабских уголовников. В конце апреля Одесский губком сформировал Временное рабоче-крестьянское правительство Бессарабии, вскоре перебравшееся из Одессы в Тирасполь. Его возглавил И. Н. Криворуков. 28 апреля политбюро компартии Украины приняло решение о формировании Бессарабской Красной армии. Через Бессарабию и Буковину советские войска собирались двинуться на помощь красной Венгрии.
Первого мая советское правительство предъявило Румынии ультиматум с требованием в 48 часов очистить Бессарабию и Буковину (последняя, кстати сказать, была австрийской провинцией и никогда не входила в состав Российской империи). 5 мая 1919 года, совершив переправу, в Бендеры ворвалась небольшая группа большевистских повстанцев. Они докладывали советскому командованию: «Пять часов утра. Переправа совершена удачно. Румынская застава взята без выстрела. Часовые других постов спали и также сняты. Цепь из сорока штыков, направившаяся в сторону Бендерской крепости, заставила последнюю выкинуть белый флаг о сдаче. Другой небольшой отряд захватил вокзал, откуда без всякого боя бежали жандармы и румынские солдаты». Однако к концу дня румынские войска выбили повстанцев из Бендер. Штаб Котовского в это время находился в гостинице «Швейцария» в Тирасполе. Казалось, его отряд скоро ринется за Днестр.
Однако 7 мая поднял мятеж освободитель Одессы начдив 6-й советской дивизии, бывший штабс-капитан царской армии, георгиевский кавалер и бывший полковник армии УНР Николай (Никифор) Александрович Григорьев, прототип атамана Грициана Таврического из популярной советской оперетты Бориса Александрова «Свадьба в Малиновке», экранизированной в 1967 году. Он отказался выступить на Румынский фронт и выдвинул лозунги «власть Советам народа Украины без коммунистов», «Украина для украинцев», «свободная торговля хлебом». Отличились григорьевцы и еврейскими погромами. Войска Григорьева, насчитывавшие до двадцати тысяч человек, взяли власть в Александровском, Елисаветградском, Херсонском уездах. Советские гарнизоны в Кременчуге и Золотоноше восстали и присоединились к Григорьеву. Повстанцы заняли Екатеринослав и Николаев, но 21 мая были разбиты на подступах к Киеву превосходящими силами советских войск, частично снятых с Бессарабского фронта. Григорьев с отрядом в три тысячи человек присоединился к Нестору Махно, но был заподозрен последним в сношениях с деникинцами и 27 июля 1919 года убит.
Писатель Иван Бунин, находившийся в те дни в Одессе, в связи с восстанием Григорьева записал 11 мая в дневнике: «Во избежание циркулирующих в городе слухов, штаб Третьей украинской советской армии объявляет, что атаман Григорьев, собрав кучку приверженцев, провозгласил себя гетманом и объявил войну Советскому правительству… Затем приказ Антонова-Овсеенко: „Белогвардейская сволочь стремится расстроить красную силу, натравить ее на мирное население… Подлый предатель родины, подлый слуга врагов наших Каин должен быть уничтожен, как бешеная собака… раздавлен и вбит, как черви, в землю, которую он опоганил…“