The club was founded in 1960 as Krasnoye Znamya Vitebsk (Red Flag Vitebsk). They began playing in Soviet Class B (second-tier league) the same year. After three seasons they relegated to the third tier. Vitebsk team would spend almost all of their subsequent Soviet-era seasons playing at the third level (Soviet Second League), with the exception of 1970 and 1990, when the team dropped to 4th level. The club went through several name changes. In 1963 they were renamed Dvina Vitebsk after local river. In 1985 they renamed to Vityaz Vitebsk and in 1989 to KIM Vitebsk (both names relate to local industry companies).
In 1992 KIM joined Belarusian Premier League. During the 90s KIM (later renamed to Dvina Vitebsk again in 1994 and Lokomotiv-96 Vitebsk in 1996) was one of the league top teams. They were league runners-up in 1992–93 and 1994–95, finished third in 1993–94 and 1997 and also won Belarusian Cup in 1998. Since 2000s club's results declined. They have relegated to the First League several times and promoted back and were never able to fight the title in later years. In 2003 they shortened their name to Lokomotiv Vitebsk and in 2006 to the current version, FC Vitebsk.
1 Separate cup for 3rd level teams, different for each zone.
2 Relegated due to Class B (the league where Dvina was playing) changing its status from 3rd to 4th level in 1970, and the top two levels were reorganized into three with fewer teams.
3 Promoted due to 3rd level (Class A Second Group, renamed to Second League since next season) expansion from 3 to 6 territorial zones (from 66 to 124 teams) in 1971 and dismissal of 4th level.
4 In 1973 every draw was followed by a penalty shoot-out, with a winner gaining 1 point and loser gaining 0.
5 Despite finishing 13th from the 22 teams in 1989, KIM relegated as the Second League (3rd level) was reduced from 9 zones (195 teams) to 3 zones (66 teams) and the Second Lower League with 9 zones was introduced as a 4th level.