Первая и последняя жертва Генри Старра — заместитель маршала из округа Новато Флойд Уилсон. В тот роковой день 1892 года Уилсон опознал Старра и попытался задержать его. Он выстрелил первым, но промахнулся. Выстрелить второй раз он не успел: Старр точным выстрелом в сердце уложил его наповал.
Всю первую половину следующего 1893 года Генри Старр посвятил ограблениям. 5 марта его банда напала на поезд у Приора в штате Оклахома и поживилась 6 тысячами долларов. Во время налета Генри в одном из вагонов познакомился с некой мисс Мэри Моррисон. Она так ему понравилась, что он узнал ее домашний адрес, и эта связь в конце концов привела их к алтарю. Эта свадьба, собственно, и заставила Генри Старра впервые задуматься о своей судьбе. Быть грабителем до конца своих дней он уже не желал и в начале лета решился на свое последнее ограбление.
6 июня его банда напала на банк в Бентонвилле, штат Арканзас и захватила 12 тысяч долларов. Этих денег Старру и его жене вполне хватило, чтобы уйти от погони и спрятаться в Колорадо-Спрингс. Теперь перед молодоженами маячила долгая и счастливая семейная жизнь. Однако действительность оказалась куда как печальнее. Один из местных жителей опознал в добропорядочном джентльмене бандита и грабителя и тут же дал знать об этом полиции. 4 июля 1893 года Генри Старр был арестован.
Состоявшийся вскоре суд признал Генри Старра виновным в убийстве заместителя маршала Флойда Уилсона и приговорил его к повешению. Однако в тюрьме Старр умудрился совершить героический поступок. Когда 26 июля 1895 года из тюрьмы Форт-Смита попытался бежать известный нам "Чароки Билл" именно Генри Старр вступил с ним в переговоры, во время которых и уговорил его прекратить сопротивление и сдать оружие. За этот поступок Старру заменили смертную казнь 13 годами тюрьмы. Он отсидел восемь лет и вышел на свободу в 1904 году.
Однако, став торговцем недвижимостью, Старр недолго оставался добропорядочным гражданином. Имея скромную зарплату, он вспоминал о том, как ему за один налет удавалось получить сразу несколько годовых зарплат. И Генри Старр не выдержал.
13 марта 1908 года вместе со своим старым компаньоном Кидом Уилсоном Старр напал на банк в городке Тиро и «заработал» 2500 долларов. Прошло немного времени, и вот уже летом они ограбили банк в Амите, штат Колорадо, сорвав куш в несколько тысяч долларов. С этими деньгами можно было жить в свое удовольствие в каком-нибудь тихом городке, и Старр уже собирал вещи, чтобы так и сделать. И в этот момент его арестовали в Аризоне в самом начале 1909 года.