«Известие о том, что царь спасся, подействовало на Халтурина самым угнетающим образом. Он свалился совсем больной и только рассказы о громадном впечатлении, произведенном 5 февраля на всю Россию, могли его несколько утешить, хотя никогда он не мог примириться со своей неудачей и не простил Желябову того, что называл его ошибкой».
Угнетенный своей неудачей, Халтурин уехал на юг России, где около двух лет занимался пропагандой среди рабочих, но чрезвычайное осадное положение, введенное в Одессе, а особенно деятельность Стрельникова, предназначенного Александром III производить следствия по политическим делам на всем юге России и снабженного особыми полномочиями, вскоре стало сильно мешать Степану. Он известил об этом «Исполнительный Комитет», который и поручил ему организовать убийство всесильного и всем ненавистного прокурора. Поручение это было удачно выполнено 18 марта 1882 года Халтуриным и его товарищем Желваковым. Подробности об этом убийстве описаны в корреспонденции из Одессы, напечатанной в № 3 «На родине», в 1883 году.
«18 марта господин Стрельников, пообедавши по обыкновению во французском ресторане, вышел на бульвар для обычной послеобеденной прогулки и, пройдясь несколько раз по средней аллее, сел на скамейку у прохода из крайней аллеи на среднюю, от которой она отделяется изгородью, окружающей ряд деревьев. Рядом с ним сел один подозрительный субъект, который в Новороссийском университете выдавал себя то за студента Энгельгарда, то за вольнослушателя Смирнова. Когда Желваков, все время следивший за Стрельниковым, подходил к скамейке, нащупывая в кармане револьвер, Стрельников встал и пересел на соседнюю скамейку, оглядывая вполоборота средние аллеи. Желваков остановился у конца изгороди, за которой сидел Стрельников, вынул револьвер и, прицелившись в правую сторону затылка, спустил курок. Голова Стрельникова мгновенно склонилась на правый бок и оперлась о спинку скамейки. Публика так и замерла на месте: никто не шевельнулся даже и тогда, когда через мгновение на крайней аллее появился человек с револьвером в руке и, перепрыгнув через изгородь, пустился вниз по крутому спуску к Гаванной улице. Он поравнялся уже с зданием думы, когда Смирнов, подбежав к краю аллеи и махая руками, стал кричать вниз: „Ловите! Держите!.. Убили среди бела дня!..“
Тогда ожила и публика на бульваре; послышались голоса: „за доктором!“. Одна барыня решилась даже подойти к Стрельникову и приложить платок к ране, но ее заботы оказались напрасными: он был уже мертв. Через несколько минут появился Гурко (роковая скамейка стоит как раз против его дворца) и воскликнул: „какие беспорядки!“, приказал отнести еще теплый труп Стрельникова в ближайшую больницу. Появилась, наконец, и полиция, начавшая свою деятельность с отобрания адресов у присутствующих». «Желваков между тем бежал вниз, отстреливаясь от нагонявших его или пытавшихся преградить ему путь. Все, кто видал этот бег и эту необычайную защиту на узком и крутом спуске, не могли хладнокровно говорить о силе, ловкости и самообладании молодого героя. Выпустив все заряды из двух револьверов, он выхватил кинжал и, продолжая отбиваться, приближался все более к белой лошади, запряженной в пролетку, на которой поджидал его Халтурин у конца узкого спуска, выходящего на Гаванную улицу. Между тем внизу перед спуском собралась уже кучка прохожих. Они не знали, конечно, что совершилось там наверху, но с изумлением смотрели на несущегося к ним вооруженного человека, поранившего уже многих, пытавшихся задержать его. Им скоро стала заметна цель этого отчаянного бега; многие бросились к выходу спуска, чтобы в этом узком месте задержать бегущих, и окружили пролетку. В эту критическую минуту Халтурин, убедившись, что Желвакову пробиться к пролетке невозможно, соскочил с нее и, выхватив револьвер, хотел поспешить на помощь к товарищу, но на первых же шагах он споткнулся. Еврей, приказчик из угольного склада, околоточный надзиратель и несколько карантинных рабочих бросились его задерживать. „Оставьте! Я социалист! Я за вас!“ — крикнул Халтурин. Рабочие инстинктивно остановились. „Чтобы ты так жил, как ты за нас!“ — ответил приказчик, здоровенный негодяй, вместе с околоточным всею тяжестью навалившийся на Халтурина. „Конечно, не за таких мерзавцев как ты, а за рабочий несчастный народ!“ — проговорил тот, с трудом переводя дыхание. Подоспевшая полиция помогла им связать Халтурина и зверски скрутить ему руки глубоко впившимися в тело веревками.