Точная дата рождения Матвея Гагарина неизвестна, исследователи склонны полагать, что он появился на свет в 1659 году. Карьера Гагарина началась со службы в Сибири: с 1693 года он был воеводой в Нерчинске — городе, расположившимся на русско-китайской границе. Гагарин разделял стремление Петра I к преобразованиям и всячески старался отличиться в службе. Однако уже тогда Гагарина подозревали в незаконной торговле с Китаем.
В 1706 году Петр I сделал его «главным человеком» Сибирского приказа. До этого времени Матвей Гагарин руководил строительством каналов, в частности, соединением Невы и Волги. Проделанную работу отметил царь. Следующий этап карьеры Гагарина — руководство укрепительными работами московского Кремля и Китай-города.
Гагарин быстро становится одним из самых богатых людей в России. Фасады его домов в Москве и Санкт-Петербурге поражали воображение простых и зажиточных горожан. До сих пор на Тверской улице красуется четырехэтажный особняк Гагарина в венецианском стиле, построенный итальянским архитектором Джованни Фонтана.
Пик политической карьеры Гагарина приходится на 1708 год, когда по приказу Петра I Россия была поделена на 8 губерний. Сибирская губерния, самая крупная из них, перешла в руки Матвея Гагарина. Согласно воспоминаниям современников, губернатор тесно сотрудничал со шведскими военнопленными, находившимися в Сибири. Он всячески помогал солдатам, жалуя им деньги на все необходимое для жизни и лично выслушивая просьбы и жалобы пленных. Граф Карл Пипер писал, что князя «будут вечно помнить в Швеции».
В 1712 году князь уехал в Тобольск, где возглавил строительство каменного кремля. Строителями были шведские военнопленные. Тогда для шведских детей в Тобольске была открыта школа и кукольный театр, куда впрочем ходили и дети русских чиновников. К тому времени вопросы, касающиеся нелегальной торговли с Китаем и долгов по таможенным сборам, по-прежнему стояли остро. Гагарина неоднократно вызывали в Петербург, где шло расследование.
Положение князя усугубила история с якобы найденными месторождениями золота в Сибири. В 1715 году под руководством подполковника Бухольца туда была отправлена экспедиция для поиска месторождений и строительства крепостей для добычи драгоценного металла. Тогда золото не нашли, однако была построена Омская крепость, и тем самым основан город. В летописи тобольского ямщика Черепанова сохранилось упоминание о строительстве Омской крепости: «Князь Гагарин, получа известие от подполковника Бухолца, нетокмо представление ево за благо принял, но и послал к нему для дополнения полков 1300 рекрут в трёх партиях и так немедленно крепость по реке Оми строить начали». Несмотря на то, что многие современники свидетельствовали о добросовестной работе Матвея Гагарига, неудачу экспедиции повесили на него.
Гагарин полностью утратил доверие царя. 14 (25) марта он был приговорен к смертной казни. Через два дня Гагарин был повешен, его труп висел на улице семь месяцев, чтобы другим казнокрадам неповадно было.