Футбольный клуб «Спартак» был образован в столице Кабардино-Балкарии в 1935 году. В 1952 году – дебютировал в первенстве РСФСР. С 1959 по 1965 годы – выступал в классе «Б» чемпионата СССР, с 1966 по 1970 годы – во второй группе класса «А». 1965 год стал знаковым для нальчикского коллектива. Спартаковцы блестяще провели сезон, сначала одержав победу в зональном турнире класс «Б», а затем – в полуфинале и финале чемпионата РСФСР. За это достижение тринадцати футболистам команды было присвоено звание «Мастер спорта СССР». В 1968 году во второй группе класса «А» среди соперников «Спартака» был и севастопольский СКЧФ. По ходу сезона моряки дважды уступили нальчанам – в гостях – 0:2, и в Севастополе – 0:1.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
Спартак Нч. – СК КЧФ 2:0
12. 06.1968. Нальчик. Стадион Спартак. 10000 зрителей.
СК КЧФ: Астаповский, Галущенко, Струнин, Осадчук, Мелешко,
Зайцев, Шевчишин, Никитенко (Чеботок), Колодин, Попов, Бурлаков.
Старший тренер – М.И. Ермолаев.
СК КЧФ – Спартак Н. 0:1
30.09.1968. Севастополь. Стадион СК КЧФ. 6200 зрителей.
СК КЧФ: Астаповский, Мелешко, Струнин, Абрамян, Галущенко,
Зайцев, Осадчук (Чеботок), Колодин, Хливецкий, Шевчишин, Киселев.
Старший тренер – М.И. Ермолаев.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
С 1971 по 1991 годы спартаковцы выступали во Второй и Первой лигах отечественного футбола. Они трижды становились победителями зональных турниров Второй лиги (1971, 1977 и 1978 гг.), но только дважды преодолевали сито переходных матчей за право играть в Первой лиге (1971 и 1978 гг.), где в общей сложности провели семь сезонов. В 1981 году команда из столицы Кабардино-Балкарии вернулась во Вторую лигу, оставаясь там до 1991 года (лучшее место – 2-е в 1985 году). В 1986 году на зимнем первенстве российского республиканского совета ДСО "Спартак" в Москве севастопольская "Атлантика" встречалась на групповом этапе с нальчикским "Спартаком". Тогда соперники разошлись миром - 1:1.
В 1992 году в I чемпионате России «Спартак» выступал в Первой лиге, однако в 1994 году вновь оказался – во Второй. В Первый дивизион команда вернулась в 1996 году, а в 2005-м – поднялась в Премьер-лигу. В классе сильнейших «Спартак» играл с 2006 по 2012 годы, заработав почётное звание «грозы авторитетов». Наивысшим достижением команды стало 6-е место по итогам сезона 2010 года. В период с 2000 по 2006 годы в коллективе из Нальчика успешно выступал воспитанник севастопольского футбола Анатолий Скворцов, сыгравший за «Спартак» 218 матчей и забивший 12 мячей.
По итогам чемпионата 2011/12 гг. нальчане опустились в Первый дивизион. После двух не самых удачных сезонов последовал вылет во Второй дивизион и возвращение на один сезон обратно – в Первый. Начиная с первенства 2017/18 гг., «Спартак-Нальчик» беспрерывно выступает во Второй лиге, где выше шестого места не поднимался.
Домашние матчи команда проводит на Республиканском стадионе «Спартак» в Нальчике (вместимость - 13800 мест).