The club was founded in 1930 under the name Bardhyli Lezhë and participated in the Albanian Superliga for the first time in 1937 where they finished in sixth place out of ten clubs. The club then changed its name to SK Lezhë in 1949, Puna Lezhë just two years later in 1951, Fitorja Lezhë in 1958 and finally Besëlidhja Lezhë in 1968.
In 2006/07 season, the club played in the Albanian Second Division. They were promoted to the first division for the 2007/08 season. But for the 2008/09 season they have again been relegated to the Kategoria e Parë 2008-2009.