FK Cement was founded in 1913 by the employees of a Beočin cement company and Mr. Martin Bajer, a native of Beočin who received his formal education in Budapest where he first got the idea of founding a football club.
The first starting line-up of the team in 1913 was:
goalkeeper: Dejan Đurić
defenders: Martin Bajer and Dragutin Karasik
right midfielder: M. Daraboš
centre midfielder: Vladislav Eseš
left midfielder: J. Daraboš
right winger: Brana Jovičić
right forward: Dejan Krkljus
centre forward: Herbst
left forward: Tipman
left winger: Aleksandar Jegdić
This starting line-up was featured until 1919 under the club name BAK. From 1919 to 1932 the team was known as BSK.
From 1922 to 1927 there were two football clubs in Beočin, the other one being FK Radnički. Radnički was dissolved in 1927 due to financial difficulties and the exodus of some players to the BSK. At that time, BSK featured the following players: Martin Bajer, Janika Sabo, Rudolf Kovačić, Oto Košćal, Josip Bajer, Franja Babi, Karlo Kapošvarc, Franja Mesinger, Janika Oltvanji, Nikola Dvoržak, Ladislav Eseš, D. Manjoki, Martin Dvoržak among others.
Since 1933 the club has been known as FK Cement. Up until World War II, the club included players such as Mile Stojkov, Franja Buršl, Franja Ferić, Rudika Nozak, Leopold Popović, Vilim Rakšanji, Florika Major, Stevan Vajs, Janika Košćal, Ivan Gabrić, Žaki, Ivica Horvat and others.
In 1970, during its 50-year anniversary celebrations, the club was honoured by the Football Association of Yugoslavia as one of the oldest in the country.