Первая и последняя жертва Генри Старра - заместитель маршала из округа Новато Флойд Уилсон. В тот роковой день 1892 года Уилсон опознал Старра и попытался задержать его. Он выстрелил первым, но промахнулся. Выстрелить второй раз он не успел: Старр точным выстрелом в сердце уложил его наповал.

Всю первую половину следующего 1893 года Генри Старр посвятил ограблениям. 5 марта его банда напала на поезд у Приора в штате Оклахома и поживилась 6 тысячами долларов. Во время налета Генри в одном из вагонов познакомился с некой мисс Мэри Моррисон. Она так ему понравилась, что он узнал ее домашний адрес, и эта связь в конце концов привела их к алтарю. Эта свадьба, собственно, и заставила Генри Старра впервые задуматься о своей судьбе. Быть грабителем до конца своих дней он уже не желал и в начале лета решился на свое последнее ограбление.

6 июня его банда напала на банк в Бентонвилле, штат Арканзас и захватила 12 тысяч долларов. Этих денег Старру и его жене вполне хватило, чтобы уйти от погони и спрятаться в Колорадо-Спрингс. Теперь перед молодоженами маячила долгая и счастливая семейная жизнь. Однако действительность оказалась куда как печальнее. Один из местных жителей опознал в добропорядочном джентльмене бандита и грабителя и тут же дал знать об этом полиции. 4 июля 1893 года Генри Старр был арестован.

Состоявшийся вскоре суд признал Генри Старра виновным в убийстве заместителя маршала Флойда Уилсона и приговорил его к повешению. Однако в тюрьме Старр умудрился совершить героический поступок. Когда 26 июля 1895 года из тюрьмы Форт-Смита попытался бежать известный нам "Чароки Билл" именно Генри Старр вступил с ним в переговоры, во время которых и уговорил его прекратить сопротивление и сдать оружие. За этот поступок Старру заменили смертную казнь 13 годами тюрьмы. Он отсидел восемь лет и вышел на свободу в 1904 году.

Однако, став торговцем недвижимостью, Старр недолго оставался добропорядочным гражданином. Имея скромную зарплату, он вспоминал о том, как ему за один налет удавалось получить сразу несколько годовых зарплат. И Генри Старр не выдержал.

13 марта 1908 года вместе со своим старым компаньоном Кидом Уилсоном Старр напал на банк в городке Тиро и "заработал" 2500 долларов. Прошло немного времени, и вот уже летом они ограбили банк в Амите, штат Колорадо, сорвав куш в несколько тысяч долларов. С этими деньгами можно было жить в свое удовольствие в каком-нибудь тихом городке, и Старр уже собирал вещи, чтобы так и сделать. И в этот момент его арестовали в Аризоне в самом начале 1909 года.

Суд не пошел на снисхождение и приговорил Генри Старра к 25 годам тюрьмы. За его спиной вновь захлопнулась тюремная дверь, и, казалось, удача навсегда отвернулась от этого человека. Выйти на свободу ему теперь предстояло в возрасте 61 года, а это был уже закат жизни. Но Генри Старр и на этот раз сумел перехитрить судьбу.

В заключении он вел себя настолько идеально, что уже в 1913 году власти штата решили освободить его досрочно с условием, что он никогда не появится в их штате. Старр такое слово дал и в тот же день был отпущен.

Вернувшись в свой родной округ Талса Генри Старр около двух лет вел себя вполне законопослушно, но в 1915 году его терпение иссякло. К тому времени у него родился сын, и он решил обеспечить его будущее испытанным методом.

27 марта его банда совершила невероятное в тогдашней криминальной истории Америки: в один день в городе Страуд, штат Оклахома они напали сразу на два банка и завладели 5 тысячами долларов. Однако в момент отхода Генри Старру не повезло. Некий 15-летний Поль Курри, оказавшийся невольным свидетелем ограбления, принес из соседней лавки ружье и прицельным выстрелом ранил Старра в ногу.