В мае 1908 года в отставку по собственному желанию ушел князь Васильчиков. Столыпин объяснял это личными мотивами: «С князем Васильчиковым у меня никаких разногласий не было. Князь Васильчиков сам настойчиво домогался ухода по своим домашним обстоятельствам, и после того, что смета его прошла в Думе и Совете, ходатайство его было уважено». Сам князь в кулуарах жаловался на то, что не находит поддержки своей деятельности по проведению земельной реформы. Однако царь рассудил, что «помоему, ему просто надоело служить и хочется заняться своими собственными делами и сделаться свободным. Это жаль, потому что он хороший человек, с настоящим именем». Зато сменивший его на столь важном посту по представлению Столыпина (знакомый его по Гродно, где у него жили мать и сестра) управляющий Дворянским земельным и Крестьянским поземельным банками Александр Кривошеин (выпускник физмата) оказался настоящим кладом для премьера, оставаясь ему верным до конца. А впоследствии идеи Столыпина претворял в жизнь уже будучи главой правительства юга России при Врангеле в Крыму в 1920 году. По свидетельству известного русского поэта Ивана Тхоржевского, в то время чиновника Министерства земледелия, Столыпин и Кривошеин «отлично дополняли друг друга. Один – вождь, рыцарь, весь – сила и смелость. Другой – такт, расчет, осторожность. И оба – энтузиасты. Энтузиасты не самодержавия, как называют их слева, а великой России, нуждавшейся в исторической скрепе власти».
В марте 1909 года был уволен Редигер. Премьер не смог простить министру то, «что он два раза в Думе не только не ответил против речи Гучкова, но согласился с ним и этим не защитил честь армии». Более того, генерал, рассчитывая получить поддержку Думы, раскрыл перед комиссией государственной обороны все дефекты военной организации. А это вообще-то должностное преступление. Следует заметить, что сменивший его уже по желанию царя киевский генерал-губернатор, генерал от кавалерии Владимир Сухомлинов (председатель Киевского отдела «Русского собрания»), личность одиозная, с самого начала вызвал неприязнь у премьера. Хотя бы уже потому, что тот вынужден был мириться с этой креатурой не только самодержца, но и, по слухам, самого Распутина. Дальнейшее с лихвой подтвердило мнение Столыпина. Именно Сухомлинова считали главным виновником плохого снабжения русской армии накануне Первой мировой войны. 13 июня 1915 года после «горлицкого прорыва» немцев опозорившийся вконец генерал был уволен от должности военного министра, а затем обвинен в государственной измене, противозаконном бездействии, превышении власти, служебных подлогах и лихоимстве. Арестован, судим и приговорен к бессрочной каторге уже при Временном правительстве.
В морском ведомстве перемены были чаще. В январе 1907 года Бирилева сменил старый адмирал Иван Диков (участвовал гардемарином еще в Севастопольской обороне), развивший на этом посту активную деятельность по исправлению ошибок Русско-японской войны и допущению в морской корпус не только дворян, но и разночинцев. В январе 1909 года 76-летнего адмирала сменил вице-адмирал Степан Воеводский из свиты государя и по личной протекции того. Новый морской министр стал настоящим «якорем» на пути преобразований флота, затеянных его предшественником, и Столыпин приложил максимум усилий, чтобы убрать царского протеже с этого поста. В марте 1911 года премьеру удалось-таки сменить того на одного из героев осады Порт-Артура адмирала Ивана Григоровича, сумевшего затеять масштабную кораблестроительную деятельность. Со Столыпиным ему так и не пришлось до дела поработать, но характерной чертой правильности выбора премьера может являться тот факт, что построенные усилиями Григоровича накануне и в ходе Первой мировой войны боевые единицы составляли 100 % линкоров, 40 % крейсеров и 30 % эсминцев, встретивших в 1941 году Великую Отечественную войну.
После сокрушительного поражения российской дипломатии в ходе Боснийского кризиса (Россия фактически поддалась на ультиматум Германии, прекратив поддержку Сербии и согласившись на аннексию Боснии и Герцеговины Австро-Венгрией) в отставку был отправлен Александр Извольский. Его функции с мая 1909 года фактически исполнял бывший министр-резидент при папе римском Сергей Сазонов (землевладелец Рязанской губернии, женатый на Анне Нейдгардт, сестре Ольги Борисовны – жены Столыпина).
В январе 1909 года генерал-лейтенант Шауфус был отправлен в отставку, как запустивший работу железнодорожного ведомства. Если в год его назначения в России было построено 2504 верст путей, то в последующие годы этот показатель упал до нуля. Сменивший его выпускник юрфака Петербургского университета Сергей Рухлов ситуацию переломил и ежегодно умудрился наращивать сеть на 5 тысяч верст, как истинный государственник, занялся выкупом в казну частных железных дорог и впервые добился их бездефицитной работы.