Bešlija started his career with hometown side Slaven Živinice. Although he was among the youngest players in their squad, he became an important part of the first team. He was spotted there and signed by Bosna Visoko, a first division team at that time, in 1997. He spent two seasons in Visoko, during which he was selected for the national U21 team. His rapid footballing ascent attracted the interest of FK Željezničar and he signed for them in 2000, becoming a fans' favourite during his single season in the capital.
Bešlija joined Racing Genk in July 2001, where he stayed for five years, and made over 130 league appearances, and he won the Belgian League with them in 2003-04. He moved to Heart of Midlothian during January 2006 in a deal worth £850,000 (€1.22 million), a record fee paid by the Tynecastle side. A dispute developed about whether the overall transfer fee should include agents percentages or not, leading Hearts to suspend payment after the first installment. When further dialogue brought no resolution, Genk petitioned UEFA to impose a transfer embargo upon Hearts, however, agreement was finally reached in December 2006, with Hearts paying the entire outstanding balance.
Beslija suffered serious injury problems with Hearts and he failed to win a regular first team place. He was loaned out to Belgian club Sint-Truidense for the 2007–08 season, and he was released by Hearts in October 2008 after they reached a severance agreement.
On the international level, Bešlija has not played for Bosnia since 2006 mainly due to several injuries and loss of form at club level. He retired from international football in 2007.