The club was formed in September 1972 as Ballshi i Ri, and they played in the Albanian Third Division between 1973 and 1976. But between 1976 and 1981 they were not allowed to participate in Albanian football due to laws restricting a single team from each district. They began playing once again in the Third Division in 1981, which they eventually won in 1986 and were promoted to the Albanian Second Division. The club played in the Second Division for 10 years between 1986 and 1996, where they were promoted following a successful 1995-96 season which saw the club score 124 goals and concede just 21, making it a national record which was even noted by prestigious French magazine France Football. However, despite their record breaking season they finished as runners-up in the league but still achieved promotion to the Albanian Superliga.
In their debut season in the top flight of Albanian football the club finished in 14th place out of 18 teams. During the 1998-99 season the club finished in third place, just 2 points behind the eventual champions KF Tirana this earned the club a place in the UEFA Cup for the first time. In their first European experience KF Bylis played Slovakian side FK Inter Bratislava, whom they lost 5-1 to on aggregate. The following season they would again finish strongly, this time in 5th place, joint on points with 4th place side Vllaznia Shkodër, who they lost 4-3 to in the play-off for the UEFA Intertoto Cup place. In the 2000-01 season they finished 5th once again and earned a place in the UEFA Intertoto Cup, where they met Romanian side FC Universitatea Craiova the following season. They lost 4-3 on aggregate, after a memorable 3-3 draw away in Romania and a 1-0 home loss.
KF Bylis then began to struggle, eventually getting relegated after a poor 2002-03 season which saw they finish second to last with just 26 points and 3 wins from 26 games. They were relegated once again to the third tier after the 2004-05 season in which they scored just 13 league goals in total. Between 2007 and 2009 the club achieved back-to-back promotions back to the Albanian Superliga for the 2008-09 season.
Besnik Kapllanaj was the club's president between 2006 and 2014 and owned a 75% share in the club, with the remaining 25% owned by the Ballsh Municipality.
On 15 March 2014 in a home tie against KF Laçi the club's president was involved in an altercation with the FSHS head of competitions, Besnik Çela. Kapllanaj hit the FSHF delegate Çela in the head with a baton which required him to be rushed to hospital due to the injury. Cela refused to start the game due to overcrowding inside the Adush Muça Stadium. Once some of the fans had left the they began to throw rock into the stadium in disapproval of the FSHF's decision to not let them watch the match, which kicked off 20 minutes later than scheduled. Kapllanaj then allegedly caused a power cut so that SuperSport Albania cameras could not transmit the game live as was planned. In the closing stages of the game KF Laçi were awarded a penalty which caused crowd trouble, as they began to throw rocks onto the pitch. KF Laçi's president Pashk Laska instructed captain and penalty taker Erjon Vuçaj to miss the penalty intentionally to avoid further trouble and danger for his teammates. Following the final whistle Kapllanaj physically abuses KF Laçi's players by hitting them with a baton, as well as Besnik Çela, who later filed a police report against Kapllanaj once he left the hospital. On 19 March the club's president Besnik Kapllanaj resigned from his post hours before the verdict from the FSHF disciplinary commission, who punished him with a lifetime ban from sporting activities in Albania. The commission also expelled the club from the Albanian Superliga with 9 remaining games of the 2013-14 season, relegating the club to the Albanian First Division for the 2014-15 season as well as handing KF Laçi a 3-0 victory in the game which originally ended 0-0.The following day Kapllanaj turned himself in to the Fier police authorities after being charged for assault.