Bešlija started his career with hometown club 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 won both the Bosnian Cup and Supercup. His rapid footballing ascent attracted the interest of Željezničar and he signed for them in 2000, becoming a fan favorite during his single season in the capital. He won three trophies in that period with Željezničar, one Bosnian Premier League title, one cup and one Supercup.
Bešlija joined Genk in July 2001, where he stayed for five years, and made over 130 league appearances, winning the Belgian First Division title with them in 2002. He moved to Scottish side Heart of Midlothian during January 2006 in a deal worth £850,000 (€1.22 million), a record fee paid by the Tynecastle side at the time.[1] A dispute developed about whether the overall transfer fee should include agents percentages or not, leading Hearts to suspend payment after the first installment.[1] When further dialogue brought no resolution, Genk petitioned UEFA to impose a transfer embargo upon Hearts,[2] however, an agreement was finally reached in December 2006, with Hearts paying the entire outstanding balance.[3]
Bešlija suffered serious injury problems at 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 was released by Hearts in October 2008 after they reached a severance agreement.[4]
In 2009, he re-signed with Željezničar and retired in 2012, winning four more trophies in the process, two leagues and two cups.[5]
