В момент образования (1796 год) губерния делилась на 8 уездов: Кольский, Кемский, Онежский, Шенкурский, Холмогорский, Архангельский, Пинежский и Мезенский (перечислены с запада на восток).
В 1859 году был упразднён Кольский уезд (восстановлен в 1883 году).
В 1891 году от Мезенского уезда отделена восточная часть, образовавшая Печорский уезд с центром в Усть-Цильме. В 1899 году Кольский уезд был переименован в Александровский, центр уезда был перенесён из Колы в основанный в этом же году город Александровск (ныне — Полярный).
В 1903 году административное деление губернии имело следующий вид:
В 1918 году образован Усть-Вашский уезд.
В 1921 Александровский уезд преобразован в отдельную Мурманскую губернию; в те же годы Кемский уезд отошёл к Карельской трудовой коммуне, а часть Печорского — к Автономной области Коми(Зырян).
В 1922 году упразднен Усть-Вашский уезд, Холмогорский уезд переименован в Емецкий (упразднён в 1925 году). В 1927 году упразднён Пинежский уезд.
В 1929 году при ликвидации губернии были ликвидированы и все её уезды.