The original club was founded as SK Sloga in 1920.[1] They were, however, banned by the authorities after just a year. In 1925, the club continued its activities as RSK Valjevo and was led by some founding members of the previous club. Their first recorded game occurred in 1926. In 1929, the club changed its name to FK Budućnost.[1] They became members of the Belgrade Football Subassociation in 1930.[1]
In 1959, the club merged with FK Radnički to form FK Metalac. They earned promotion to the Yugoslav Second League in 1969.[2] In 1971, the club changed its name back to FK Budućnost.[2] They spent two more seasons in the second tier of Yugoslav football.[2]