В январе 1906 года случилось неизбежное: Котовского опознали и арестовали. В Кишиневской тюрьме он получил кличку Кот и стал признанным авторитетом. Кот вмешивался в порядки тюремных обитателей, устраивал расправы над неугодными. В мае того же года он занялся организацией побега семнадцати уголовников и анархистов. План казался красивым: самим переодеться охранниками и вывести всех, якобы направляя осужденных по этапу. Обезоружив трех надзирателей и забрав у них ключи от ворот, беглецы сначала решили выпустить всех уголовников. А те живут по принципу «каждый сам за себя». В тюрьме подняли тревогу, прибыла рота солдат и конных стражников, которые и водворили тринадцать беглецов, включая Котовского, обратно в камеры. Котовский после этого пытался бежать еще дважды и через полгода добился успеха.
В полицейских сводках можно найти словесный портрет уголовника, откуда мы узнаем, что росту в нем было всего 174 сантиметра (в то время как многие наделяли его «богатырским двухметровым ростом»), телосложение он имел плотное, немного сутулился, отличался «боязливой» походкой и слегка покачивался при ходьбе.
Далее в портрете говорится о карих глазах, круглой голове с небольшими усами, редкими черными волосами и залысинами на лбу. Имелась и особая примета — странные черные точки под глазами: это была татуировка пахана, блатного авторитета. Уже после революции Котовский всячески старался избавиться от этих наколок, выжигал и вытравливал их. Григорий был левшой, владел стрельбой «по-македонски», то есть с двух рук, и начинал всегда с левой. Он знал, не считая родного русского, также немецкий, молдавский и еврейский языки. Умел произвести впечатление вежливого, интеллигентного человека, вызывать симпатию.
Полицейские сводки — и современники согласны с ними — в один голос описывают огромную силу Котовского. С самого детства он поднимал тяжести, занимался боксом, был большим любителем скачек. И это ему очень пригодилось в жизни, а особенно в тюрьме. Ведь сила здесь означала независимость и власть, позволяла запугивать врагов и прочих жертв. Так что в ту пору описать Котовского просто: это пудовые кулаки, буйный норов и тяга к удовольствиям. Если он не скучал на тюремных нарах и не разбойничал на большой дороге, то прожигал награбленное в дорогих ресторанах, публичных домах, а также на скачках.
Появившись в городе, он выдавал себя за элегантного и родовитого богача, называл себя помещиком или коммерсантом, управляющим или представителем какой-либо фирмы, машинистом, уполномоченным по заготовке провианта для армии… Котовский часто посещал театры, хвастался своим исключительным аппетитом и пристрастием к породистым лошадям, азартным играм и красивым женщинам.