Дружина быстро прославилась, уничтожая провокаторов, вымогая деньги у разного рода фабрикантов, владельцев отелей и ресторанов. Как правило, Котовский подбрасывал жертве письмо, в котором требовал выдать ему деньги «на революцию». Именно диверсионно-террористическая дружина «революционера» Котовского способствовала тому, что Япончик утвердился как король бандитов Одессы, ведь он считался революционером-анархистом. Между Котовским и Япончиком тогда не существовало особых различий: оба были рецидивистами, бывшими каторжниками и анархистами. Совместно с бандитами Япончика дружина Котовского осуществила нападение на одесскую тюрьму, освободив множество заключенных, она же громила конкурентов Япончика, «бомбила» склады, магазины, кассы. Общее восстание бандитов и революционеров на Молдаванке, в пригороде Одессы, состоявшееся в конце марта 1919 года, тоже было их совместной операцией.
В тот момент, когда белогвардейцы стали покидать Одессу, стягиваясь к порту, дружинники Котовского, воспользовавшись хаосом и паникой, разыскивали на улицах города офицеров и убивали их.
О периоде «подпольной» жизни Котовского в Одессе почти не сохранилось достоверных сведений. Не очень убедительно выглядят рассказы Котовского о работе в одесском большевистском подполье с самого апреля 1918 года. Ведь в Одессе его помнили только с ноября 1918 года — и то не как подпольщика, а в лучшем случае как «народного мстителя», а то и простого грабителя, осуществлявшего налеты как на частные жилища, так и на государственные конторы. Ходили также смутные слухи о том, что якобы осенью 1918 года Котовский воевал вместе с Махно.
В настоящих документах большевистского подполья нигде не встречается имя Котовского. Вот почему ему отказали в просьбе считать его партийный стаж с 1917-го или с 1918 года. Собравшаяся в 1924 году партийная комиссия пришла к выводу, что Котовский начал сотрудничать с партией лишь весной 1919 года. Однако Котовский и дальше пытался обмануть партийный контроль, утверждая, что его отряд громил петлюровцев уже в декабре 1918 года. Но иногда он прокалывался, вспоминая, что в тот период вел партизанскую войну в Бессарабии, нападая на румынских полицейских.
Как только в Одессе установилась советская власть, Котовский был назначен новыми властями на первую официальную должность — он стал военкомом Овидиопольского военного комиссариата. В то же время ему поручили сформировать группу для подпольной борьбы в Бессарабии. Однако как может городок с семью тысячами обитателей, с гарнизоном в шестьдесят штыков удовлетворить амбиции бывшего Атамана Ада? Должность командира конного отряда из восьмидесяти человек, входившего в 44-й стрелковый полк 3-й украинской армии, несомненно, понравилась ему больше; проблема заключалась лишь в том, что это подразделение существовало только на бумаге из-за банального отсутствия лошадей. Вспомнив юность, Григорий Иванович предложил угнать коней у соседей-румын. Группа из сорока человек под его предводительством форсировала Днестр и напала на конный завод в 15 километрах от границы, откуда увела почти сотню отличных скаковых лошадей.
И вот 3 июня 1919 года Григорий Иванович Котовский получил первую значительную должность, став командиром 2-й пехотной бригады 45-й стрелковой дивизии. Первым проверочным заданием для Котовского было подавление недовольства крестьян-старообрядцев одного из сел Одесской губернии. Шесть дней повстанцы держали оборону в своем селе, но в итоге карательный отряд справился с задачей, утопив бунт в крови. Восставшие получали подмогу из соседних сел, потому пришлось «карать» и их. А уже через две недели Котовский подавил восстание немецких крестьян-колонистов, а также «умиротворил» петлюровское село. Соединение Котовского переименовали в 12-ю бригаду 45-й дивизии. Сперва ее использовали в качестве прикрытия по Днестру со стороны Румынии. Но с наступлением петлюровских войск, с конца июля 1919 года, Котовский со своей бригадой удерживал фронт в районе Ямполь — Рахны.
На помощь к Котовскому Советы выслали полк имени Ленина под командованием Мишки Япончика. Полк полег почти весь после первого же сражения. Но не будем пока забегать вперед — ведь рассказ о Короле еще впереди. После того как полки Стародуба и Япончика были самым бесславным образом разгромлены, часть входивших в них одесских бандитов и немногим от них отличавшихся матросов вошла в 402-й полк бригады Котовского. Легендарный комбриг стал для них лучшим покровителем: он отдавал захваченные села солдатам на разграбление.
Новая легенда о Котовском возникла летом 1919 года. Якобы он собирался во главе пяти тысяч конников выступить против Румынии и отвоевать у нее Бессарабию, после чего оказать помощь венгерским революционерам. Но опять этому не находится никаких документальных свидетельств.