The first generation of Celje players started to practice small arena handball, and played their first game on concrete, on the open, in front of the local railway station.

In the meantime, talented players from the youngster team of Celje (such as Persinger, Telič, the Goršič brothers etc.)

led by Jože Kuzma with the help of Tone Goršič and Franc Ramskugler had become 4 time consecutive vice-champions of the youngster First Republican League.

Celje managed to stay in the first division for three seasons, when it was once again relegated to a newly established Second Yugoslavian Federal Handball League in 1971.

The Celje team was playing in the second division for four full seasons, gaining valuable experience and skill.

The work on the young players had paid off, for in 1976, in the new Golovec Hall, Celje beat Velež Mostar in the qualifications, and once again became a member of the first division.

The success of regaining a place amongst the elite obviously had a positive impact, because the Celje team managed to come to three Yugoslavian Cup finals, although all three of them were lost to Partizan in 1976, Medveščak in 1978 and Metaloplastika in 1980.

He was also part of the team on 1976 Montreal Summer Olympics, making him the most successful Slovenian player, who played for Celje.

In the 2003–04 season, Celje became the European champions after defeating SG Flensburg-Handewitt in the final with an aggregate score 62–58 over two legs.