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.