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