До этих пор карьера Горемыкина складывалась удачно. Однако 20 октября 1899 года, находясь в заграничной поездке по Англии и Франции, он неожиданно для себя и без всяких объяснений был уволен с должности министра внутренних дел. Император назначил Ивана Аоггиновича всего лишь членом Государственного совета с оставлением в должности сенатора. Ему было уже почти шестьдесят семь лет, и казалось, что карьера стареющего юриста клонится к закату.

Но судьбе было угодно распорядиться по-другому. Вследствие различных придворных интриг и борьбы противоположных групп, окружавших императора Николая II, Горемыкин все же сумел «взлететь» на чиновничий Олимп. Он стал премьер-министром и возглавил правительство Российской империи. До него юристы редко когда поднимались так высоко. По мнению современников, назначению Горемыкина способствовала рекомендация Д. Ф. Трепова, бывшего столичного генерал-губернатора, а затем дворцового коменданта, «полу-диктатора», как отзывались о нем некоторые приближенные к императору вельможи. Как писал С. Ю. Витте, Трепов рассчитывал, что Горемыкин на посту председателя Совета министров будет во всем слушаться его советов, и даже подготовил для него инструкцию, как вести себя в Государственной думе. Но его надежды не оправдались. 22 апреля 1906 года, перед самым открытием первой Государственной думы, кабинет премьер-министра С. Ю. Витте пал, и на место председателя Совета министров был поставлен Горемыкин, который одновременно оставался членом Государственного совета и сенатором. В правительстве произошли основательные перестановки, были заменены все министры (за исключением трех: военного, морского и торговли).

27 апреля 1906 года в Георгиевском тронном зале Зимнего дворца состоялось торжественное открытие Государственной думы и преобразованного Государственного совета. После торжественного молебна император произнес «тронную речь». Из Зимнего дворца депутаты направились в Таврический, где в четыре часа был отслужен еще один молебен, а в пять часов все заняли свои места в зале заседаний. Весь кабинет министров во главе с Горемыкиным поместился в ложе министров, а члены Государственного совета – в своей ложе. По поручению императора открыл Государственную думу статс-секретарь 3. В. Фриш. Председателем Думы избран был С. А. Муромцев.

Государственная дума сразу же заявила свои права «на верховную власть». После горячих прений она выработала так называемый адрес, в котором было указано, что спокойная и правильная работа Думы может происходить только при условии ответственности всех министров перед народными представителями и что необходимо «освободить Россию от действия чрезвычайных законов». Дума предлагала выработать законы о полном уравнении всех граждан независимо от национальности и пола, о равноправии крестьян и охране наемного труда, о всеобщем бесплатном обучении, справедливом распределении налогов, преобразовании местного управления и самоуправления на началах всеобщего избирательного права. Она высказалась за аграрную реформу и наделение крестьян землей за счет принудительного отчуждения земель частнособственнических, казенных и удельных, за отмену смертной казни и исключительных законов, за проведение полной политической амнистии.

Ответить на все эти запросы предстояло председателю Совета министров Горемыкину. 13 мая 1906 года ему пришлось выступить в первой Государственной думе со своей программой. Он заявил, что Совет министров, полагая в основании своей деятельности соблюдение строгой законности, готов оказать полное содействие разработке всех вопросов, поднятых Государственной думой.