Родился 11 ноября 1979 г. в Москве.
В 2004 г. окончил Московский государственный социальный университет Министерства труда и социального развития РФ (ныне Российский государственный социальный университет) по специальности "социология".
С 1999 г. работал на руководящих должностях в ИТ-компаниях, в том числе в ЗАО "Аррава интернет менеджмент" и холдинге IBS Group. В 2003-2004 гг. был директором по развитию бизнеса IBS Group.
В 2004 г. был назначен советником министра информационных технологий и связи РФ Леонида Реймана. 6 февраля 2006 г. стал директором департамента госпрограмм, развития инфраструктуры и использования ограниченного ресурса этого ведомства. После того, как в мае 2008 г. вместо Министерства информационных технологий и связи было создано Министерство связи и массовых коммуникаций РФ во главе с Игорем Щеголевым, Шадаев занял в нем пост директора департамента государственной политики в области информатизации и информационных технологий.
Осенью в 2008 г. Максут Шадаев стал помощником руководителя Администрации президента РФ Сергея Нарышкина, отвечал за организацию работы совета при главе государства по развитию информационного общества, а также за проект создания биометрических паспортов.
В феврале 2009 г. был включен в первую сотню резерва управленческих кадров президента РФ.
В 2012 г. стал советником председателя Государственной думы РФ Сергея Нарышкина. Отвечал за реализацию проекта "Электронный парламент".
С 11 февраля 2014 г. по 14 сентября 2018 г. Максут Шадаев был министром государственного управления, информационных технологий и связи Московской области (глава правительства региона - губернатор Андрей Воробьев). 29 сентября 2016 г. также стал заместителем председателя правительства Подмосковья. Под руководством Максута Шадаева был запущен портал "Добродел" (единая книга жалоб и предложений Московской области). После ухода из правительства региона он занимал пост советника губернатора Андрея Воробьева на общественных началах.
С 2017 г. Максут Шадаев также был советником на общественных началах первого заместителя руководителя Администрации президента РФ Сергея Кириенко. Сообщалось, что он консультировал власти на тему работы в социальных сетях.
С сентября 2018 г. - вице-президент телекоммуникационной компании "Ростелеком" по цифровым платформам, с февраля 2019 г. совмещал этот пост с должностью гендиректора АО "РТ лабс", дочерней компании "Ростелекома".
С 21 января 2020 г. - министр цифрового развития, связи и массовых коммуникаций РФ в правительстве Михаила Мишустина. Сменил во главе ведомства Константина Носкова. 14 мая 2024 г. переназначен на должность. В Госдуме в поддержку его кандидатуры проголосовали 373 депутата из 448, против - 1, воздержались - 57.
Член совета директоров "Аэрофлота" (с июля 2020 г.), Почты России (с декабря 2020 г.).
Действительный государственный советник Московской области I класса.
Награжден орденом Почета (2010), медалью ордена "За заслуги перед Отечеством" II степени (2019).