Teams from Gomel (usually city or raion selection or railway-based team Lokomotiv, but not always) played in Belarusian SSR championships since early 20's. In 1946 Belorusian SSR league for one season becomes one of the zones of USSR 3rd level league, and Lokomotiv Gomel became the first city team to play in Soviet league.
The modern Gomel team was founded in 1959 as Lokomotiv Gomel. They played at the 2nd level of Soviet football between 1959 and 1968. The results varied between seasons, as the team managed to finish 1st in their zone in 1962 as well as last in 1959 and 1963. However, because Soviet league system structure was changing almost every season in 50's and 60's, Lokomotiv wasn't promoted or relegated until another league reorganization in 1969.
Gomselmash played at the 3rd level of Soviet football between 1969 and 1989, until further league reorganization in 1990, after which the team was relegated to the 4th level.
In 1992 Gomselmash joined the newly formed Belarusian Premier League. The first years were unsuccessful and the team relegated in 1995. They changed name to the current one, FC Gomel, the same year. In 1998 Gomel returned to Premier League and achieved much better results than before (champions title in 2003, 2nd place in 2007 and 3rd in 1999). The team also won Belarusian Cup in 2002 and made it to the final in 2004.
In 2012 they played English club Liverpool in the UEFA Europa League qualifying rounds. In the first leg they lost 0–1 and lost again away at Anfield in the second leg 3–0.
1 Finished last in its zone, but saved from relegation due to 2nd level (Class B) expansion from 7 to 9 territorial zones (from 101 to 142 teams) in 1960.
2 No promotion to the Top League in 1962 was awarded due to Top League (Class A) reduction from 22 to 20 teams in 1963. Lokomotiv's play-off performance didn't affect its next season league allocation. Winning their zone allowed them to stay on the second level (Class B), which was reduced from 10 zones (150 teams) in 1962 to a single group of 18 teams in 1963.
3 Finished last, but saved from relegation due to 2nd level (Class A Second Group) expansion from 18 to 27 teams in 1964.
4 Play-off with the best-placed Belarusian team from the 3rd level (Class B) in 1968 for the right to play on the 2nd level (Class A Second Group) in 1969.
5 Play-off with the lowest-placed Belarusian team from the 2nd level (Class A Second Group) in 1969 for the right to play in Class A Second Group (which becomes the 3rd level league next year due to introduction of Class A Top Group as the Top level) in 1970.
6 Finished last in its zone, but saved from relegation 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.
7 In 1973 every draw was followed by a penalty shoot-out, with a winner gaining 1 point and loser gaining 0.
8 Though finished 14th from the 22 teams in 1989, Gomselmash 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.