The club was founded in 1930 as Leka i Madh Përmet (English: Alexander the Great Përmet), following the merger of the Vjosa and Nemërçka sports associations, which had been founded in 1924 and 1926, respectively. They first competed in a national competition in the 1932 Albanian First Division, where they were in Group C along with SK Narta, Shqiponja Gjirokastër and eventual group winners SK Vlorë. They competed in the following 1933 Albanian First Division, where they were once again in Group C with Nimet Abazi Delvinë, Shqiponja Gjirokastër, Vetëtima Himarë and group winners in consecutive years SK Vlorë. They did not compete in the 1934 competition and as there was no competition held the following year they were to return for the 1936 Albanian First Division, where they to compete in Group C along with Nimet Abazi Delvinë and Drita Gjirokastër. Leka i Madh Përmet won the group and progressed to the finals stage, which was held in Durrës between the 27th and 29 July 1936, and was competed between Leka i Madh Përmet, Bardhyli Lezhë and Shkumbini Peqin. They lost their opening finals game against Bardhyli Lezhë 7–2 but went on to defeat Shkumbini Peqin 3–0, to finish second in the finals stage behind Bardhyli Lezhë.
There were no official lower tier football competitions held in Albania between 1937 and 1948 due primarily to events of World War II, meaning sports clubs in Albania ceased operations or at best were severely restricted in their activities. In 1945, the club's name was changed to 24 Maji Përmet by the Communist Party of Albania who had just taken control of the country, in order to mark the date of the communist congress held in the city in 1944. The club restarted its activities in 1949 when they competed in Group 8 of the Albanian First Division but did not progress past the first stage of the competition. The following season the Albanian First Division was held in a knockout format, and they defeated KF Tepelena 1–0 on aggregate over two legs to progress to the second round, where they were beaten 14–4 on aggregate by Tomori Berat following 9–2 and 5–2 losses. In 1951, the ruling Party of Labour of Albania forced every team in the country to change their name and 24 Maji were to be called Puna, which literally translates to Labour, and in the 1951 Albanian First Division Puna Përmet as they were now called competed in Group 7 but did not progress out of the initial group stage. They did not compete competitively again until 1954 where they were put in Group 5 of the Albanian First Division, and once again not progressing past the first stage.
