27 ноября 1891 года Горемыкин становится товарищем министра юстиции (министром тогда был Н. А. Манасеин), с 1894 года – сенатором и управляющим межевой частью на правах товарища министра. В апреле 1895 года он покидает Министерство юстиции и переходит в Министерство внутренних дел на должность товарища министра, оставаясь при этом сенатором. Этим назначением он был обязан обер-прокурору Святейшего синода К. П. Победоносцеву, который рекомендовал его императору, хотя сам министр И. Н. Дурново предпочел бы видеть на этом месте других кандидатов. Карьера продолжает складываться блестяще – спустя полгода Горемыкин становится управляющим Министерством внутренних дел, а 6 декабря 1895 года, опять же с помощью Победоносцева, его утверждают в должности министра внутренних дел.
Как происходило это назначение, рассказал в своих воспоминаниях С. Ю. Витте, в то время министр финансов, а впоследствии – председатель Совета министров: «– А что вы думаете по поводу назначения Горемыкина? – спросил меня государь. Я ответил, что Горемыкина я сравнительно очень мало знаю, ничего о нем определенного сказать не могу, но что вообще Горемыкин производит на меня впечатление человека порядочного, причем добавил, что, по всей вероятности, Константин Петрович (Победоносцев. – Авт.), между прочим, рекомендует Горемыкина потому, что Горемыкин правовед и Константин Петрович тоже правовед, а известно, что правоведы, так же как и лицеисты, держатся друг за друга, все равно как евреи в своем кагале. И если, – сказал я, – у вашего величества никого больше не имеется в виду, то, может быть, вы решитесь назначить Горемыкина? Государь ответил: – Да, я назначу Горемыкина».
Русское общество, которое, как известно, большей частью негативно относилось ко всем царским министрам, сразу же откликнулось на это назначение несколькими сатирическими стихами, ходившими по рукам. В одном из них, названном «Антон Горемыка», все предыдущие министры внутренних дел выводились как «горемычные души». Заключительная строфа содержала едкий каламбур: «Да, обманчивой надежде, / Говорю тебе, не верь, /Горе мыкали мы прежде, /Горемыкин и теперь». По иронии судьбы Горемыкин в числе официальных лиц года присутствовал на торжествах по случаю коронования императора Николая II в мае 1896 года, закончившихся, как известно, Ходынской катастрофой.
На посту министра внутренних дел Иван Аоггинович оставался в течение пяти лет, но эти пять лет изменили его до неузнаваемости. По словам С. Ю. Витте, Горемыкин до назначения министром был человеком «довольно либерального направления», но, вступив в должность, «под влиянием свыше, боясь себя скомпрометировать, начал вести довольно реакционную политику».
О взглядах Горемыкина писали и другие мемуаристы. Вот мнение В. И. Гурко, служившего в то время в Государственной канцелярии: «Прослужив в течение долгих лет в Сенате, правда не по судебному, а по второму, так называемому крестьянскому, департаменту, Горемыкин невольно впитал в себя приверженность к законности и отрицательное отношение к административному произволу. По природе, несомненно, умный, тонкий и вдумчивый, с заметной склонностью к философскому умозрению, он считался не только либералом, так как по личным связям принадлежал к либеральному сенаторскому кружку, но даже сторонником, конечно, платоническим, толстовского учения. Выдающейся чертой характера Горемыкина и его умственного настроения, чертой, с годами все больше в нем развивавшейся, было ничем невозмутимое спокойствие, очень близко граничившее с равнодушием». Годы, когда Горемыкин был министром внутренних дел, были для Российской империи нелегкими. Министерству пришлось бороться с так называемыми неурожайными бедствиями и в связи с этим значительной миграцией крестьян. В 1896 году Горемыкин был вынужден даже создать особое Переселенческое управление в системе Министерства внутренних дел. Были учреждены установления по крестьянским делам Акмолинской области и временные положения о крестьянских начальниках Тобольской, Томской, Енисейской и Иркутской губерний. При нем были несколько ужесточены законы об ответственности губернаторов за совершенные преступления по должности, утверждены нормативные уставы сельских пожарных дружин и потребительских обществ. Во все эти вопросы Иван Логгинович вникал досконально. При Горемыкине министру юстиции Н. В. Муравьеву удалось «урвать» (выражение С. Ю. Витте) у Министерства внутренних дел Главное тюремное управление. Причем сделано это было в обход Государственного совета.