Byen nævnes første gang i memoirerne af præsten Dukljanin hvor han nævner at grev Bele-Pavlimir besejrede ungarere i "dalen Belina". Bijeljina nævnes også den 3. marts1446, da en handelsmand fra Dubrovnik blev røvet her.
Bijeljina har i de sidste 500 år udskiftet den komplette befolkning. Første gang var det ved ankomsten af tyrkerne i 1520 og den anden gang ved ankomsten af Østrigerne i 1716.
Serberne fra denne område støttede opstanden anført af Karadjordjević, men den mislykkedes og serberne fra området led en stor nederlag i forsøget at befri serberne fra tyrkerne i tiden fra 1875-1878.
Før krigen boede der mange bosniakker i byen, men langt de fleste af dem er blevet fordrevet.
