Spartak Varna was founded on 28 August 1918 by a group of young people, who were playing football together for two years. At the initial meeting, regarding the establishment of the club, the name was decided to be SC Sokol. Niagol Kolev was elected as the first chairman of the club. A few days later, the members of the board registered the Football Club to the government under the name "Bulgarski Sokol". The colors of the team were blue and white. "Bulgarski Sokol," one of the poor suburban teams in Varna, is poorly circumstanced in comparison to the leading teams at that time such as Ticha and "Vladislav." Nonetheless, the football team quickly became stronger, and improved their style of play.
On 30 January 1924 "Bulgarski Sokol" merged with the sport club "Shipka". These days the team proved itself as one of the strongest teams in Varna. Among all the players called with a lot of love from the fans "Falcons" with most successful plays was the forward Mihail Tunchev. In 1924 he was invited in the national team and that way he became the first national player of the team.
A few years later started the rise of the team. In the season 1928/29 the team won for the first time the championship of Varna, and joined the State Championship where they reached third place. Two years later 1930/31 the falcons were again champions of Varna. For the State Championship they reached the final with the Sofia's AS-23. Next year "Shipchenski Sokol" again reached the final, where the rival was the capitol's team Slavia. On 18.09.1932 in front of 10 000 audience on the football field of AS-23 the falcons won with 2:1 and became State Champion and Winner of the Cup of the King. In the next season "Shipchenski sokol" were again champion of Varna, and for the State Championship they reach for the third consecutive time the final. On 03.10.1933 in Sofia rival of the "falcons" was PFC Levski Sofia. Varna's team lost with 3:1 and took the second place in the State Championship.
In 1945 the club merged with other two Varna's football clubs "Levski" and "Radetski". This happened on 18.10.1945, and was accepted the name of the club to be SPARTAK. In the years between 1945–1948, three times Spartak reached the semi-finals of the State Championship. In 1950, the team took the fifth place in the newly created "A" Republican Football League. Spartak Stalin relegated to B League in 1952 but returned to A League at next year. Spartak again relegated to second level in 1963–64 season but returned in 1964–65 season. However, this return was short-lived and relegated in 1965–66.
In 1955, Spartak won the third place and bronze medals in the championship of "A" League. In 1959 the forward of Spartak Georgi Arnaudov-"Alaha" became a shooter of the championship with nine goals. Two years later, Spartak again had a winner in the shooters list: Liuben Kostov with 12 goals. In 1960/61, Spartak had very good matches in the tournament of the Soviet Army which then was playing the role of the Cup of Bulgaria. They reached the final where and meet the strongest team in Bulgaria at that time- CSKA. Spartak lost the final 3:0. As a finalist, Spartak won the right to play in the tournament of the National Cup Winners. In 1969 another sport club merged with Spartak – it was the "Lokomotiv" sport club. The merge became a fact on 06.03.1969 and the club took the name "JSK-Spartak". JSK-Spartak returned to first level in 1970–71 but relegated in 1973–74 and returned to first level in 1974–75. JSK-Spartak relegated again in 1977–78.