Родился 8 октября 1956 г. в г. Джетыгаре Кустанайской области Казахской ССР (ныне Житикара, Республика Казахстан) в семье кадровых сотрудников внутренней службы.
В 1979 г. окончил физико-математический факультет Петрозаводского государственного университета им. О.В. Куусинена.
В 1981-1982 гг. учился на Высших курсах Комитета государственной безопасности (КГБ) СССР в Минске.
Кандидат экономических наук. В 2001 г. в Санкт-Петербургском государственном университете экономики и финансов защитил диссертацию по теме: "Экономические аспекты формирования предпринимательства в современной России".
После окончания университета преподавал физику в школе пос. Надвоицы Карельской АССР (с 1991 г. – Республика Карелия).
В 1981–1994 гг. проходил службу в органах госбезопасности Карельской АССР . Служил в должностях оперуполномоченного, старшего оперуполномоченного, начальника Медвежьегорского районного отделения, начальника отдела по борьбе с терроризмом Министерства безопасности Республики Карелия. В 1992-1994 гг. работал под непосредственным руководством Николая Патрушева, занимавшего пост министра безопасности Республики Карелия.
С 1995 г. перешел на службу в центральный аппарат Федеральной службы контрразведки РФ (с апреля 1995 г. – Федеральной службы безопасности, ФСБ РФ). Занимал должности главного инспектора организационно-инспекторского управления, начальника отдела Управления собственной безопасности (УСБ) ФСБ России (УСБ в это время возглавлял Николай Патрушев).
В 1998-1999 гг. работал в Администрации президента РФ, был начальником отдела Главного контрольного управления президента РФ (начальником управления был Николай Патрушев).
С 1999 г. по 2000 г. - начальник управления по борьбе с контрабандой и незаконным оборотом наркотиков Департамента экономической безопасности ФСБ России.
В 2000-2002 гг. занимал должность заместителя директора Федеральной службы безопасности России - начальника инспекторского управления (руководитель ФСБ России – Николай Патрушев).
В 2002–2012 гг. работал в Министерстве внутренних дел РФ. 30 июня 2002 г. назначен первым заместителем министра внутренних дел РФ Бориса Грызлова, начальником Службы криминальной милиции. С 29 декабря 2003 г. временно исполнял обязанности министра внутренних дел РФ.
С 9 марта 2004 г. по 21 мая 2012 г. - министр внутренних дел РФ в правительствах Михаила Фрадкова, Виктора Зубкова и Владимира Путина. Сменил на посту главы МВД Бориса Грызлова. Под руководством Рашида Нургалиева была проведена реформа органов внутренних дел, милиция была переименована в полицию.
С 24 апреля 2004 г. по 12 августа 2016 г. - постоянный член Совета безопасности РФ, с 12 августа 2016 г. - член Совета безопасности РФ.
С 22 мая 2012 г. - заместитель, с 6 февраля 2023 г. - первый заместитель секретаря Совета безопасности РФ Николая Патрушева.
Был председателем Совета министров внутренних дел государств-участников Союза Независимых Государств (2008-2009, 2010-2011).
Входил в состав Совета при президенте РФ по развитию физической культуры и спорта, спорта высших достижений, подготовке и проведению XXII зимних Олимпийских игр и XI зимних Паралимпийских игр 2014 года в г. Сочи (2007-2012). Также был членом Совета при президенте РФ по развитию финансового рынка Российской Федерации и Совета при президенте РФ по развитию информационного общества в 2008–2012 гг.
Генерал армии (2005).
Награжден орденами Александра Невского, полный кавалер ордена "За заслуги перед Отечеством" (I, II, III, IV степеней; 2012, 2006, 2001), "За военные заслуги", Почета. Отмечен Почетной грамотой правительства РФ (2006).
Заслуженный сотрудник органов внутренних дел РФ (2006).
Почётный гражданин Республики Карелия (2006) и г. Петрозаводска (2017).
Имеет ордена Святого благоверного великого князя Димитрия Донского I степени (2005; Русская православная церковь) и Ахмата Кадырова (2006, Чеченская Республика).
Автор книги "Основные этапы совершенствования и реформирования МВД России: приоритетные задачи и результаты. По материалам расширенных коллегий МВД России за 2003-2009 годы" (2010) и др.