Однако свой опыт Шойгу старался вообще никогда не выпячивать. Тем более что отчасти именно ему Путин был обязан своим президентством: популярный глава МЧС в 1999 году возглавил избирательный список пропутинской партии «Единство», которую придумали Березовский и Волошин. Успешный результат «Единства» (второе место) фактически гарантировал Путину победу на президентских выборах, так как уничтожил конкурирующий тандем Примакова — Лужкова. Однако это не принесло создателям партии ни дивидендов, ни благодарности Путина. Березовский через год уехал в добровольную эмиграцию в Лондон, почти все губернаторы, составившие костяк «Единства», тоже в скором времени лишились своих должностей. И у самого Шойгу в первые годы президентства Путина тоже было далеко не все в порядке.
Лидер «Единства» был категорически против слияния своего детища с блоком «Отечество — вся Россия», затеянным Владиславом Сурковым. Однако мнение министра Кремль решил проигнорировать, хоть Шойгу и получил символический пост сопредседателя «Единой России» (наряду с побежденными им мэром Москвы Лужковым и президентом Татарстана Шаймиевым).
Еще сложнее складывались отношения Шойгу с новой путинской элитой — бывшими сослуживцами Путина по ФСБ, которые взяли верх в новой администрации президента. Авторитетный силовик из ельцинской команды оказался для них естественным противником. Лидером «Единой России» на выборах в Думу 2003 года стал уже не Шойгу, а новый министр внутренних дел Борис Грызлов, совершенно нехаризматичный, но послушный исполнитель, одноклассник директора ФСБ Николая Патрушева. За полгода до выборов, в июне 2003 года, Грызлов начал мощную пиар-кампанию — борьбу с коррупционерами в рядах собственного ведомства. Образ сурового, но справедливого милиционера должен был понравиться избирателям. Разоблаченных сотрудников МВД в прессе называли «оборотнями в погонах». Однако руководителем преступной группы неожиданно оказался вовсе не милиционер, а генерал МЧС, ближайший подчиненный Сергея Шойгу. Зарабатывая предвыборные очки, глава МВД попутно «закапывал» собственного товарища по партии.
Партию трясло. В ней ходили слухи, что арестованный подчиненный Шойгу дал показания против своего босса, более того, признался на допросах, что самолеты МЧС ввозили в Россию наркотики из Таджикистана. Эти слухи остались слухами, но положение министра сильно пошатнулось.
Однако лояльность и терпение помогли Шойгу пережить опалу. Единственным способом не потерять все было сохранение доступа к Путину. И здесь Шойгу смог использовать любовь президента к охоте и экстремальному отдыху, а также уникальный ресурс МЧС. По сути, Шойгу стал эксклюзивным туроператором Путина, его специалисты могли организовать путешествие Путина в любую точку России, например на родину Шойгу в Туву — маленькую живописную республику на границе с Монголией. Сам глава МЧС стал неизменным спутником Путина на охоте и рыбалке. Именно Шойгу организовывал, к примеру, рыбалку Путина и принца Альбера II в 2007 году в Туве, когда он впервые позировал перед фотографами с обнаженным торсом, а также еще более знаменитую фотосессию, сделанную в августе 2009 года, когда полуголый Путин гарцевал на лошади в ковбойской шляпе.
В ходе той поездки Шойгу фактически выступал в роли режиссера-постановщика: это он подобрал Путину ковбойскую шляпу из арсенала МЧС и выбрал дерево, на которое потом забрался Путин. Как рассказывали очевидцы, Путин тогда очень старался, чтобы фотосъемка получилась качественная: ему пришлось как минимум трижды пересечь узкую холодную реку Хемчик, пока не получился хороший кадр заплыва баттерфляем.
Через полгода произошла трагедия — в Перми сгорел ночной клуб, при пожаре погибли 156 человек. Сразу стало понятно, что виновата служба пожарной безопасности, которая неоднократно проверяла заведение и выдавала ему — за взятки — все возможные разрешения. СМИ стали писать, что подобная система характерна для МЧС, ведомства Шойгу, которое как раз и отвечает за пожарную безопасность. На положении Шойгу трагедия никак не отразилась.
В 2009 году совместное увлечение Шойгу и Путина вышло на новый уровень: они вместе возглавили Русское географическое общество, научную организацию, существовавшую с середины XIX века. Шойгу стал ее президентом, Путин — председателем попечительского совета (его предшественниками в этом качестве были императоры Николай I, Александр II, Александр III и Николай II).
Помощники Шойгу утверждают, что он действительно любит экстремальный отдых — ежегодно уходит в пешие походы по лесу, и каждый из таких походов становится огромной головной болью для ФСО, сотрудники которой не имеют права терять охраняемое лицо из виду. А следом за министром и президентской охраной по тувинской тайге бегут и офицеры Минобороны со спецсвязью и ядерным чемоданчиком.