В 2001—2002 годах одной из наиболее заметных проблем Министерства обороны стало бегство солдат из армии в большинстве случаев из-за издевательств офицеров, дедовщины, а также содержания на голодном пайке и других тягот службы. В 2001 году из армии дезертировали более 6 тыс. солдат, в 2002 – около 6 тыс. В 2002 году в конфликтах между военнослужащими вследствие неуставных отношений погибли около 70 человек. В комитеты солдатских матерей за 2002-й обратились в общей сложности 2867 дезертиров. На очередное коллективное бегство 24 военнослужащих 4 января 2003 года из воинской части в Ленинградской области Иванов отреагировал публичными обвинениями в адрес «так называемых комитетов солдатских матерей», само существование которых, по его мнению, провоцирует солдат на дезертирство. По мнению Иванова, эти комитеты финансируются из сомнительных источников («Кто их содержит, на что они живут – это еще вопрос»).

В первые путинские годы Сергей Иванов напоминал тень президента, которая всегда несколько отстает от хозяина. Владимир Путин едва ли не насильно толкал армию к профессионализации, а Иванов доказывал, что это слишком дорого для страны. После 11 сентября 2001 года Иванов заявил, что даже теоретически не может представить возможности размещения НАТОвских баз в странах СНГ, а Путин буквально через несколько дней благословил развертывание этих баз.

Впоследствии тень слилась с хозяином. Путин стал с удовольствием повторять вслед за Ивановым сентенции об успехах в военном строительстве. Ставить на повестку дня требования Шанхайской организации сотрудничества о выводе баз США с территории стран Средней Азии. Рассказывать о чудодейственных боеголовках, способных преодолевать американскую систему ПРО.

Это трогательное единение обусловило выдвижение Иванова на роль почти официального преемника. Один язвительный наблюдатель заметил, что нынче вся политическая борьба в России свелась к борьбе между Первым (разведка) и Вторым (контрразведка) главками бывшего КГБ. Как раз бывшие коллеги и попытались несколько подпортить образ Сергея Борисовича: и Генеральная, и Главная военная прокуратура вдруг стали публично разоблачать армейскую преступность, а государственные телеканалы подали трагедию Андрея Сычева как сенсацию, когда такие случаи происходят в армии чуть ли не ежедневно.

Во время визита министра обороны Сергея Иванова в Армению 25 января 2006 года, его спросили: «Что у вас там случилось в Челябинске?». «Я в последние несколько дней находился высоко в горах и о том, что произошло в Челябинске, не слышал, – не растерялся Иванов. – При этом думаю, что ничего серьезного. Иначе я бы об этом обязательно знал». Практически все в России к тому времени уже знали о трагедии рядового Челябинского танкового училища Андрея Сычева, который, как позднее постановил суд, лишился обеих ног в результате издевательств со стороны «дедов». Военный прокурор Александр Савенков воспользовался этим громким случаем, чтобы развернуть кампанию против дедовщины и лично министра. Савенкова поддерживал его шеф – генпрокурор Владимир Устинов, родственник и друг Игоря Сечина.

Но у Иванова оказался очень влиятельный ангел-хранитель. Например, про «правую руку президента» Игоря Сечина в 2000 году Путин высказался так: «Он попросился со мной в Москву, и я его взял». В отношении Иванова были употреблены совсем другие слова – «чувство локтя».

После нескольких месяцев нервотрепки министр вышел из схватки победителем: в июне Владимир Путин снял генпрокурора Валентина Устинова, которого позже назначил министром юстиции, а Савенкову до сих пор не нашлось теплого места ни в одном ведомстве. А еще через несколько месяцев Иванова ждал еще один карьерный рывок – пост вице-премьера.