Команда организована в ноябре 1959 года. В разные годы называлась 1959-1960 – «Спартак», 1961-1963 – «Текстильщик», 1964-1966 – «Текмаш», 1967-1991 – «Спартак», 1992 – «Звольма-Спартак», с 1993 – «Спартак». В чемпионатах страны постоянно участвует с 1960 года. В Классе «Б» первенства СССР (1960-1970) команда провела 356 игр (149 побед, 116 ничьих, 91 поражение), 459 голов забито, 367 пропущено. Лучшее достижение – 2-е место в зоне (1963, 1966, 1967, 1968, 1970). Худшее – 14-е (1960, 1965). Во Второй лиге Первенства СССР (1971-1980, 1983-1991) команда провела 700 игр (308 побед, 172 матча сыграны вничью, 214 поражений), 954 гола забито, 751 мяч пропущен. Лучшее достижение – 1-е место (1973, 1980). Худшее – 17-е место (1991). В Первой лиге (1981-1982) «Спартак» провёл 88 игр (20 побед, 25 ничьих, 43 поражения), 67 мячей забито, 127 пропущено.
Лучшее достижение – 12-е место (1981), худшее – 22-е место (1982). В Российской истории «Спартак» в сезонах 1992-2017/18 играл во Второй лиге (1992, 1993, с 1998) и Третьей лиге (1994-1997) ПФЛ. Лучший результат – 2-е место в зоне «Запад» сезоне 2011/12. В 2018 году клуб утратил профессиональный статус. Перед началом сезона 2022/23 получил профессиональный статус и право выступать во Второй лиге. В сезоне 2025-2026 костромской «Спартак» впервые дебютирует в Первой российской лиге. Из знаменитых футболистов, воспитанников Костромы, лучшим считают Георгия Ярцева. Чемпион СССР и России в составе «Спартака» (как игрок в 1979 и как тренер в 1996), тренер сборной России на Евро-2004. Тренер года в России по версии РФС 1996 и 2003 гг. Выступал за клуб в 1965-1967 и 1975-1976 гг.)
Команды Красноярск («Локомотив») и Кострома («Текмаш») впервые встретились в полуфинальном турнире Победителей зон класса «Б» в 1966 году в Туле. Оба матча, состоявшиеся 21 и 27 октября завершились с одинаковым счетом 0:0. Сегодняшний матч в первенстве России первый в истории команд, а вот в Кубке России сегодняшние соперники уже играли в Костроме 26 сентября 2024 года в матче 1/32 финала Пути регионов Кубка России сезона 2024/25. Красноярский «Енисей» на выезде уступил «Спартаку» из Костромы: встреча завершилась со счётом 0:1.