Клуб, как считается, основан в 1935 году. Именно провел свой первый матч предшественник нынешнего «Спартака». Та команда называлась «Динамо». Команда вскоре вышла в лидеры на уровне Кабардино-Балкарии, регулярно побеждая в местных чемпионате и кубке. А вот на всесоюзный уровень выбралась только дин раз, проведя сезон 1946 в третьей группе первенства СССР, в Северокавказской зоне.

1959—1965 годы «Спартак» провел в классе «Б», где добыл победу в своей зоне и в 1965 и выиграл финальный турнир чемпионата РСФСР. С 1966 по 70-е спартаковцы выступали во в основном второй группе класса «А», где взяли серебро в своей зоне в 1970, а также стали чемпионами РСФСР. На 80-е пришлось безуспешное пребывание во второй лиге.

После распада Нальчик оказался в новой первой лиге, из которой вылетел через два года, В 1995 Нальчик выиграл вторую лигу, но в первой его выступления долгое время были очень нестабильными.

В 2004 году команду на тренерский мостик взошел экс-тренер дубля Юрий Красножан. С ним связывают последующие успехи клуба — борьбу за выход и сам выход в 2005 году без солидной финансовой поддержки и достойной инфраструктуры.

6 августа 2007 года 10 российских футболистов «Спартака» торжественно вступили в ряды «Единой Россит», поскольку, как они признались, пребывать в этой партии очень престижно, а кроме того, в ней состоит президент Кабардино-Балкарии и главспонсор команды Арсен Каноков.