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. They played top level in 1937, 1950, 1952, 1970–71, between 1972–1975, 1978–79, between 1980–1983, between 1984–1986, between 1987–1990, between 1993–1996, between 2000–2003 and 2007–2008.
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.