В апреле 2005 года член Совета федерации РФ Виталий Мутко на внеочередной отчетно-выборной конференции избран президентом Российского футбольного союза. В этой должности он заменил ушедшего в отставку Вячеслава Колоскова, который руководил РФС четверть века.
Одной из первых инициатив Виталия Мутко на новом посту было введение лимита на легионеров. В высшем дивизионе его фактически не существовало. С 2006 года начало действовать правило, согласно которому на поле в составе одной команды не может находиться одновременно более семи иностранцев. С 2009 года их количество было сокращено до шести. Лимит многократно превращался в тему для дискуссий в экспертном сообществе. Причем его роль получала диаметрально противоположные оценки — как позитивные, так и негативные.
Спустя год после избрания Виталия Мутко РФС подписал контракт с голландским тренером Гусом Хиддинком, который возглавил сборную страны. До этого национальной командой руководили исключительно отечественные специалисты, а авторитетные функционеры выступали резко против приглашения на такой пост иностранца. Наиболее активным лоббистом кандидатуры Гуса Хиддинка считался Виталий Мутко. Летом 2008 года сборная под руководством Хиддинка добилась первого большого успеха в своей истории, выйдя в полуфинал чемпионата Европы, который принимали Австрия и Швейцария.
В январе 2009 года Россия, еще никогда не принимавшая самые главные футбольные соревнования, подала заявку в Международную федерацию футбола на проведение чемпионата мира 2018 или 2022 года. В числе основных авторов идеи фигурировал Виталий Мутко. Выборы стран—хозяек первенства состоялись в конце 2010 года — уже после того, как по распоряжению Дмитрия Медведева он оставил пост в РФС, сосредоточившись на работе в правительстве. Россия одержала сенсационную победу в борьбе за чемпионат мира 2018 года, а речь министра спорта РФ на английском языке с превратившейся в мем фразой «Лет ми спик фром май харт» была ярчайшим моментом презентации ее заявки.
В сентябре 2015 года Виталий Мутко был вновь избран президентом РФС вместо ушедшего в отставку Николая Толстых. При господине Толстых финансовое положение федерации стало критическим, а общая сумма ее кредиторской задолженности на момент избрания господина Мутко превышала 2,5 млрд руб. В конце 2017 года РФС объявил, что полностью погасил долги. Значительная часть задолженности возникла из-за контракта РФС с возглавлявшим сборную России итальянцем Фабио Капелло. Различные источники оценивали годовую зарплату господина Капелло в России в сумму от €7 млн до €10 млн, считая бонусы. При этом решение о досрочном расторжении договора, рассчитанного на срок до 2018 года, после провального выступления сборной на чемпионате мира 2014 года в Бразилии привело к необходимости выплачивать господину Капелло громадную неустойку, минимальный размер которой оценивался в €21,5 млн. Она еще усугубила проблемы РФС. Виталий Мутко винил в заключении такого неудачного контракта в первую очередь Николая Толстых. Сторонники господина Толстых подчеркивали, что договор был согласован с министром спорта и тот поставил на соглашении свою подпись.
В августе 2016 года РФС рискнул назначить новым наставником сборной России Станислава Черчесова — далеко не самого рейтингового специалиста, которого поддерживал лично глава организации. Риск оправдался. Под руководством господина Черчесова российские футболисты через два года совершили прорыв на домашнем чемпионате мира, выйдя в четвертьфинал.