The club was formed in 1950 as BSG Einheit Brandenburg and played its earliest seasons in the II division of East German football. They took on the name BSG Stahl Brandenberg in 1955 to reflect the backing of the local steel company. With that support, the club able to assemble competitive sides by offering attractive salaries to the castoffs of other teams. The strategy drew some capable players to their ranks and helped them develop a solid fan base. The side earned promotion to the DDR-Oberliga for the 1984–85 season and played there until German reunification in 1990. After a name change to BSV Stahl Brandenburg they spent the 1991–92 season in the 2.Bundesliga Nord. In 1993, with the closing of the local steel mill and the loss of their financial support, 'stahl' was dropped from the team name.
By the end of the 90's they found themselves mired in financial difficulty. The club declared bankruptcy in 1998 and quickly re-formed as FC Stahl Brandenburg, but continued to stumble. In 2002, in a desperate move to save something of the club, a merger with crosstown rival Brandenburg Süd 05 to form FC Brandenburg was put into the works, but only went as far as the union of the clubs' youth sides. Fan protests from both sides – and more money problems – caused the merger to unravel the next year. Today FC Stahl Brandenburg play in the Brandenburg-Liga (VI).