Macedońska liga była systematycznie redukowana, w sezonie 1995/1996 liczyła już tylko 15 drużyn, jednak i tym razem „cementowa” ekipa zdołała się utrzymać, zajmując 11. miejsce. Przed sezonem 1996/1997 klub przemianowano na Cementarnica 55 Skopje, ale i pod tym szyldem drużyna zagrała bezbarwny sezon zajmując 12. pozycję, szczęśliwie wyprzedzając Shkendiję Tetovo. Bez rewelacji minął i sezon 1997/1998. Za to w sezonie 1998/1999 Cementarnica uzyskała najlepszy wynik od początku swej historii, zajmując w lidze 5. pozycję. Dzięki temu miejscu w 1999 prowadzona wtedy przez Zorana Rosicia drużyna po raz pierwszy zagrała w europejskich rozgrywkach.
Przygoda z Pucharem Intertoto rozpoczęła się od dość łatwego wyeliminowania gruzińskiego klubu Kolkheti 1913 Poti (4-2 w Skopju i 4-0 na wyjeździe). W II rundzie los połączył Cementarnicę z rosyjskim zespołem FK Rostov. W pierwszym spotkaniu, rozegranym w Skopju padł remis 1-1 (gol Savova dla Cementarnicy). Ten wynik stawiał w lepszej sytuacji Rosjan, ale mogło dojść do niespodzianki – przy stanie 2-1 dla gospodarzy w 89 min. Zarko Serafimovski nie wykorzystał rzutu karnego i ta pomyłka kosztowała Cementarnicę odpadnięcie z dalszych rozgrywek. Jednak w rozgrywkach ligi macedońskiej udało się powtórzyć sukces z poprzedniego sezonu i zająć 5.