Выход один, рассудил Трутнев, — бежать. Но бежать он решил во власть. Пост градоначальника Перми, богатейшего города Урала, гарантировал личную неприкосновенность, ведь городские банки не требуют долги с мэра. В декабре 1996 года Трутнев был избран на пост мэра Перми, а через четыре года победил на губернаторских выборах действующего главу Пермской области Геннадия Игумнова. Пресса обвиняла Трутнева в агрессивных методах ведения предвыборной борьбы и разнообразных нарушениях закона, но это было делом обычным…
Мэр Перми Владимир Филь запомнился горожанам своим изречением: «Снег сам нападал, сам и растает». Конечно, молодой бизнесмен и спортсмен-каратист легко выиграл выборы, набрав в первом же туре 61 процент голосов.
В «Собеседнике» описаны некоторые подробности той предвыборной баталии. Некая частная типография взялась напечатать антитрутневские листовки. По заказу конкурентов, конечно.
— Шел 1996 год, разгул черного пиара еще не начался, поэтому и текст у нас был, по сегодняшним понятиям, вполне невинный, — вспоминает один из пострадавших в той истории. — Просто сатирически обыграли текст трутневской предвыборной листовки. У него было: «Если у вас нет тепла, требуйте по телефону такого-то, нет воды — звоните туда-то, света — туда-то». И напечатаны телефоны всех чиновников, которые за это отвечают. Сильный был ход, но мы придумали, как на него ответить. «У вас нет тепла? Купите обогреватели «Филипс» в магазинах Юрия Трутнева за 300 долларов и выше! Нет света? В магазинах Трутнева есть лампочки «всего» по 100 рублей!» Ну и так далее. Там, где в оригинальной листовке было написано «Женат. Двое детей», мы заменили «Женат. Разведен. Снова женат. Двое детей».
В ночь, когда начали печатать эти листовки, к дому директора типографии подъехали пять джипов, вызвали «шутника» поговорить, отвезли его в офис «Экса». Наутро ни одна листовка не попала на улицы Перми.
Натерпевшийся страху директор типографии написал заявление в прокуратуру. В офисе «Экса» полиграфиста обрабатывали по схеме «Ты не бойся, мы тебя небольно зарежем». Физической силы не применяли, просто задавали вопросы, а ответы записывали на видео — кто заказал компромат на Трутнева и сколько заплатил…
На следующий день о подробностях предвыборной ночи знал весь город. Но уставшая от слабых и пассивных руководителей Пермь все равно дружно проголосовала за мышцы и характер нового кандидата. А уголовное дело против членов избирательного штаба действующего мэра вскоре закрыли.
Мэра Трутнева в Перми вспоминают добрым словом. Он начал убирать на улицах снег, поставил красивые остановки, дал отмашку градостроительству, затеял чистку рядов в городской администрации. Говорят, что не забыл «подчистить хвосты» и своего бизнеса — один за другим обанкротились и позакрывались банки, у которых «Экс» брал кредиты. Главный кредитор — банк «Заря Урала» — и вовсе таинственным образом сгорел вместе со всей документацией. Претензий по суду к «Эксу» не было никаких. Тем более что большая часть разорившихся банкиров потом с комфортом расселись по теплым кабинетам администрации города и других неплохих структур. А банк «Заря Урала» в народе навсегда переименовали в банк «Заря Украла».
Кандидатуру губернатора Игумнова на выборах поддерживали Администрация Президента и собственные административные ресурсы. Трутнев противопоставил им солидную спонсорскую помощь. По слухам, поддержку ему оказывали крупнейшие бизнесмены области, к которым молва относила не только главу компании «Уралкалий» Дмитрия Рыболовлева, но и гендиректора компании «ЛУКОЙЛ-Пермь» Андрея Кузяева, также входившего в состав инициативной группы по выдвижению пермского мэра на губернаторских выборах. Говорили же, что некие «олигархические круги» хотели спровадить Игумнова на пенсию, на место которого якобы двигали «динамичного» Юрия Трутнева.
Два года губернаторства Трутнева в Перми не утихали слухи о его переезде в Москву. Говорят, президент Путин приехал в Пермский край и был очарован молодым губернским начальником, который образцово провел объединение Пермской области и Коми-Пермяцкого округа (бальзам на душу Кремля). Кроме того, привел в край компанию Вексельберга «Ренова», которая стала много строить в Перми, и потанинский «Интеррос», который получил одно из крупных предприятий края. «ЛУКОЙЛ» спонсировал автоувлечение Юрия Трутнева — участие в гонках… В общем, переезд губернатора, пришедшегося по сердцу Кремлю и нескольким ключевым олигархам, был всего лишь вопросом времени.
В 2001 году Трутнев выступил инициатором объединения Пермской области и Коми-Пермяцкого АО. При этом в прессе публиковалась информация об активном использовании губернатором «административного ресурса» для обеспечения явки избирателей. Участники референдума, состоявшегося в декабре 2003 года, подавляющим большинством проголосовали за создание нового субъекта Федерации — Пермского края.