На этом грузовичке Келли возил виски аж в Нью-Мексико — и там в 1927 году его ненадолго посадили в тюрьму. А когда его поймали на продаже алкоголя в индейской резервации, судья закатал его на полную катушку: он получил пять лет с отбыванием наказания в Левенуэрте. Там Келли подружился с налетчиками из Сент-Пола. Известно, что он оказал помощь пытавшимся бежать заключенным во главе с Фрэнком Нэшем. В 1930 году его освободили условно-досрочно. Келли направился в Миннесоту, и его приняли как своего в таверне «Зеленый фонарь». Вскоре он уже начал грабить банки.

В сентябре того же года Келли женился на Кэтрин Торн, дамочке не слишком строгой морали, родом из Оклахомы. Ее второй муж (Келли был третьим) умер при загадочных обстоятельствах. Кэтрин была заносчива, самоуверенна и любила выпить. У нее росла дочь, которую она отдала на воспитание своей матери. Из всех женщин, на которых охотилось ФБР в 1933 и 1934 годах, она бесила Гувера больше, чем кто-либо. «Кэтрин Торн Келли была одной из самых хладнокровных и расчетливых преступниц, с которыми мне когда-либо приходилось сталкиваться», — писал он в книге «Те, кто в бегах», изданной в 1936 году. Для Гувера Кэтрин была Свенгал Автомата Келли, он называл ее «свихнувшейся на мужчинах и тряпках… коварной и сообразительной преступницей-артисткой», которая сама создала своего муженька и нашла ему применение, причем он подчинялся ей беспрекословно. «Не было на свете подкаблучника хуже, чем Джордж [Автомат] Келли», — писал Гувер.

Как бы убедительно ни звучали эти слова, в архивах ФБР нет никаких документов, которые могли бы подтвердить, что Кэтрин была больше чем просто пособницей Автомата Келли. Она не смогла бы научить его грамотнее совершать преступления. Келли был паршивым грабителем: он так волновался, когда шел на дело, что иногда его даже тошнило. В конце концов налетчики из Сент-Пола — Харви Бейли, Берн Миллер и другие — отказались с ним работать. Ничуть не лучше удавались ему и похищения людей. В январе 1932 года Автомат Келли вместе с подельником похитил бизнесмена из Индианы по имени Говард Вулвертон. Этого человека Кэтрин попросту нашла в телефонной книге. Однако семья бизнесмена отказалась платить выкуп, и Келли пришлось его отпустить.

Если не считать отлучек в Чикаго и Сент-Пол на поиски партнеров, Келли постоянно проживал в доме Кэтрин на Ист-Малки-стрит в Форт-Уэрте (Техас). Супружеская пара скоро привлекла внимание местной полиции. Однако добродушный Келли сумел подружиться с копами и однажды даже помог им задержать местного взломщика. Но ему очень хотелось стать грабителем банков. Если верить Гуверу, то Кэтрин играла роль как бы пресс-атташе Автомата Келли: она повсюду похвалялась его подвигами, надеясь, что серьезные бандиты предложат ему работу. Это похоже на правду: она действительно любила хвастаться своим мужем, особенно когда перебирала лишнего. В конце концов Келли удалось войти в компанию известного в 1920-е годы налетчика Эдди Бентца, и, взяв с собой еще жулика по имени Альберт Бейтс, в 1932 году они принялись грабить банки в Вашингтоне, Техасе и Миссисипи.

Некоторое время спустя хвастовство Кэтрин достигло ушей весьма проницательного сыщика из Форт-Уэрта Эда Везерфорда, и он втерся к ней в доверие, заверив, что работает на бандитов. Когда стало ясно, что бойню в Канзас-Сити в июле 1933 года устроил Берн Миллер, Везерфорд вспомнил среди имен налетчиков, знакомством с которыми хвасталась Кэтрин, и это имя.