The club was founded in 2001 by a founding board led by Hristiyan Parvanov, Galin Mihaylov, Slavcho Tanev, Tonko Totev and Dimo Hristov. Until 2005/06 season is playing in Regional groups until the promote in V AFG under the name FC Vereya-Arsenal after merger with Arsenal Kazanlak, but after season 2006/07 Vereya-Arsenal become Arsenal Kazanlak and the 2nd team Vereya Bulsatkom moved to Stara Zagora again and was registered as FC Vereya. They won A RFG 3 times in next 5 season, getting the promotion in 2011–12 season.
In 2016, the club submitted an application for the newly restructured Bulgarian First League. On June 1, 2016, one of the new signings of the club for the upcoming season, the Brazilian Elias Alves da Silva, announced that he joined the club, as it would compete in the top league of Bulgaria, long before an official statement was given by the BFU officials on the number of the teams competing in the new league, thus sparking controversy.
Up to five non-EU nationals can be registered and given a squad number for the first team in the A PFG however only three can be used during a match day. Those non-EU nationals with European ancestry can claim citizenship from the nation their ancestors came from. If a player does not have European ancestry he can claim Bulgarian citizenship after playing in Bulgaria for 5 years.
The club's reserve team, Vereya Stara Zagora II, played in the tier four A RFG in 2015–16, where it finished on 2nd place and won the playoff against Arda Kardzhali and is playing in South-East Third League in 2016–17 season.