Постановлением Всероссийского центрального исполнительного комитета (далее - ВЦИК) от 15 июля 1929 г. в составе Северного края был образован первый на Крайнем Севере национальный округ – Ненецкий. Административным центром округа было утверждено село Тельвисочное.
В то же время постепенно рос поселок Белощелье. На берегу у Белой щельи строились дома, конторы порта, рыбтреста, кооператива "Кочевник". 10 марта 1931 года на заседании президиума Ненецкого окрисполкома было принято решение о переименовании поселка. Этот вопрос предлагалось "…передать на обсуждение масс через печать, отдавая преимущество названиям "Нарьян-Мард" и "Ненецк".
С 18 декабря 1931 г. поселок именуется "Нарьян-Мар".
В 1931 году была проведена организационная работа по выборам первого поселкового Совета. Для этого были определены границы территории поселкового Совета: поселок лесозавода, Нарьян-Мар, пос. Калюш.
10 октября 1931 года Северный крайисполком принял решение о перенесении центра Ненецкого округа в поселок Нарьян-Мар. Переезд окружных организаций и учреждений из села Тельвисочного в Нарьян-Мар послужил новым толчком к его развитию.
В декабре 1931 г. были проведены выборы в состав поселкового Совета, куда вошли: Заборцева А.Н., Данилов В.И., Моисеев М.М., Дымов А.С., Степанов Д.В., Аристова М.И.. Первым председателем поселкового Совета избран Конухин Афанасий Васильевич.
В 1932 году постановлением ВЦИК объединенному кусту выселков с поселком лесопильного завода был присвоен статус рабочего поселка Нарьян-Мар.
В 1935 году "…в связи со значительным увеличением населения, ростом культурных и промышленных учреждений центра Ненецкого округа" рабочий поселок Нарьян-Мар преобразован в город.
Нарьян-Марский городской Совет образован 10 марта 1935 года. На момент образования в его составе было 5 штатных единиц. Исполнительный комитет городского Совета проводил в жизнь решения Совета, управляя деятельностью социальных, культурных и образовательных учреждений.
В октябре 1955 г. на основании Указа Президиума Верховного Совета РСФСР был упразднен Нижне-Печорский район Ненецкого округа. Территория района была передана в административное подчинение городскому Совету.
С 1 февраля 1958 г. в административное подчинение исполкому городского Совета была передана территория Екушанского полуострова, с расположенными на нем населенными пунктами.
В декабре 1959 года Указом Президиума Верховного Совета РСФСР были ликвидированы Канино-Тиманский, Больше-Земельский и Амдерминский районы.
20 марта 1974 г. на основании решения Архангельского областного Совета на территории Ненецкого округа зарегистрирован населенный пункт нефтегазо-разведочной экспедиции №5 – поселок Искателей, административно подчиненный Нарьян-Марскому городскому Совету. В 1982 году в связи с образованием Искательского поселкового Совета пос. Искателей выведен из подчинения Нарьян-Марского городского Совета.
После событий 1991-1992 гг. была начата поэтапная реформа деятельности Советов. В структуре Нарьян-Марского городского Совета был образован Малый Совет. Он осуществлял полномочия городского Совета в период между сессиями, за исключением вопросов, решаемых только на сессиях городского Совета.
Председателями Нарьян-Марского городского Совета 21-го созыва были избраны П.Д. Семенюк, а с апреля 1992 года – С.А. Епифанова.
21 апреля 1992 г. Нарьян-Марским городским Советом было принято решение "О Положении (Уставе) о местном самоуправлении на территории Нарьян-Марского городского Совета народных депутатов". Положение установило основы осуществления местного самоуправления на территории города Нарьян-Мара и поселка Искателей.
В октябре 1993 г. Указами Президента РФ Б. Ельцина "О реформе представительных органов власти и органов местного самоуправления в РФ" №1617 от 9.10.1993 г., "О реформе местного самоуправления в РФ" №1760 от 26.10.1993 г., деятельность городских и рабочих Советов народных депутатов была снова подвергнута реформированию.
В декабре 1996 г. состоялись выборы нового состава депутатов Нарьян-Марского городского Совета ( 22-го созыва ). 29 января 1997 г. на второй сессии Нарьян-Марского городского Совета 22-го созыва были избраны: председателем городского Совета - Коваленко Г.Б., заместителем председателя - Фомин Н.А.
Постановлением Нарьян-Марского городского Совета от 10 февраля 1998 г. №60 был утвержден Устав города Нарьян-Мара (далее - Устав города). В соответствии с законодательством Российской Федерации он установил, что выборным должностным лицом, возглавляющим местное самоуправление на территории города Нарьян-Мара, является глава города (в последующем – мэр). Устав города закрепил так называемый "матрешечный" принцип построения муниципального образования. В соответствии с ним Нарьян-Мар являлся сложным муниципальным образованием, на территории которого находилось самостоятельное муниципальное образование "Рабочий поселок Искателей". Несмотря на то, что территориально пос. Искателей входил в состав города, поселок имел свой представительный и исполнительный органы, свои Устав, бюджет и муниципальную собственность.
В январе 2001 г. прошли выборы главы МО "Город Нарьян-Мар" и выборы депутатов Нарьян-Марского городского Совета 23-го созыва. Депутатами были избраны: Бычихин С.Н., Карпов Е.Н., Степанов П.Г., Честнейшин Н.А., Хабаров А.А., Хабаров В.В., Чаленко Р.И., Чупров В.Ю, несколько позже депутатами стали Нечаев М.С., Лисицинский В.С., Фомин В.Н., Бебенин А.Б.
Председателем городского Совета избран Павел Гаврилович Степанов, заместителем – Чупров В.Ю.
В октябре 2003 г. был принят Федеральный закон №131-ФЗ "Об общих принципах организации местного самоуправления в Российской Федерации", вступающий в силу с 1 января 2006 г. В соответствии со ст.11 указанного Закона, территория поселения не могла входить в состав территории другого поселения. Сложные муниципальные образования, такие, как город Нарьян-Мар, следовало преобразовать. На основании Федерального закона №131-ФЗ Собранием депутатов НАО 24.02.2005 г. был принят закон №557-ОЗ "О статусе, административных центрах и границах муниципальных образований Ненецкого автономного округа".
В соответствии с ним территория рабочего поселка Искателей была исключена из состава территории муниципального образования "Город Нарьян-Мар". Сам город Нарьян-Мар наделялся статусом городского округа. Этим же законом было создано новое муниципальное образование – Заполярный район, в состав которого вошла вся остальная территория НАО, за исключением территории городского округа.
В соответствии с окружным законодательством, 18 сентября 2005 года прошли выборы главы городского округа "Город Нарьян-Мар" и депутатов Совета городского округа "Город Нарьян-Мар" 1-го созыва. Главой городского округа был избран Л.И. Саблин. Выборы депутатов впервые проведены по 5 многомандатным избирательным округам. В результате выборов были избраны 14 из 15 депутатов Совета городского округа 1-го созыва (список прилагается).
22 сентября 2005 г., на организационном заседании Совета городского округа, по инициативе Л.И. Саблина было принято решение о создании рабочей группы по разработке проекта Устава городского округа "Город Нарьян-Мар". Окончательный вариант Устава был принят на седьмой сессии Совета городского округа 21 декабря 2005 г.
В соответствии с Уставом, 13 января 2006 г. на десятой сессии Совета городского округа, председателем Совета был избран В.Ю. Кмить. 27 февраля 2006 г. заместителем председателя Совета был избран А.Б. Бебенин.