Так, 3 октября 1872 г. епископ Полоцкий и Витебский Савва (Тихомиров) писал епископу Муромскому Иакову (Кроткову; ум. в 1885 г.), что Леонтий «неспокоен и помышляет о бегстве», поскольку «западная окраина с её иезуитским, доселе ещё не исчезнувшим духом не может служить приятным убежищем для нас, пришедших с востока». «Я... сделал кое-что довольно прочно, не сидел без пользы, полонизм поборол изрядно, – 10 ноября того же года писал Леонтий в письме епископу Тульскому и Белевскому Никандру (Покровскому), – но дух шляхетский и жидовскую меркантильность в духовенстве нашем не скоро ещё выкурить можно. Надеюсь на семинарию и училища, которые идут у меня добрым путём». В письме архиепископу Никандру (Покровскому) от 8 апреля 1874 г. Леонтий признавался, что «измучился и здоровье испортил». 25 октября 1874 г. Леонтий был переведён в Херсонскую и Одесскую епархию. С 6 по 14 ноября длилось его прощание с подольской паствой и учащимися как светских, так и духовных учебных заведений. 21 ноября Леонтий совершил первую литургию в одесском кафедральном Преображенском соборе. К весне 1875 г. были освящены тёплая церковь при одесском Успенском храме, северный придел во имя Димитрия Солунского (3 февраля 1875 г.) в греческом Троицком храме. В апреле-мае 1875 г. Леонтий совершил путешествие по епархии, посетил больше 116 приходов, Бизюков Пропасной во имя Григория, просветителя Армении, мужской монастырь, имел собеседования с 280 причтами. Вернувшись из поездки, отдал духовной консистории несколько предписаний: о перераспределении благочиннических округов, об учреждении благочиннических советов, а также окружных и благочиннических библиотек и класса иконописания при семинарии, об избрании окружных депутатов, о ведении церковноприходских летописей, о проведении воскресных собеседований в приходах, в том числе с целью преодоления распространения в народной среде штундизма. В 1876 г. началось инициированное Леонтием издание «Одесского Воскресного листка». Ежемесячно посещал семинарию, стремился бороться с уклонением её воспитанников от церковного служения. В новоустроенную семинарскую церковь пожертвовал образа Вознесения и святителей Ростовских Исаии, Леонтия и Игнатия. По инициативе Леонтия в Одессе были открыты женское епархиальное и мужское духовное училища в отдельных зданиях, а также устроено помещение консисторского архива, отремонтированы архиерейские покои. Леонтий осуществлял благотворительную деятельность через епархиальное попечительство: всего в 1875 г. на пособие заштатным священно- и церковнослужителям, вдовам и сиротам, пострадавшим от пожара, было выделено 13 тыс. руб., не считая одновременных выдач Херсонскому Перепелицинскому приюту 2 тыс. руб., Одесскому девичьему духовному училищу – 1160 руб. 16 ноября 1875 г. по инициативе обер-прокурора Д.А. Толстого Леонтий возглавил Холмскую и Варшавскую епархию. Неожиданное назначение Леонтия было вызвано недовольством императора деятельностью «нерешительного и слабого» Холмского архиепископа Иоанникия (Горского), который, по мнению архиерея, стал «жертвою интриги» галицийского духовенства.