 In the next couple of years the club struggled to get back on a winning streak, and only managed to win the 2004 and 2006 national cup (Radivoj Korać Cup) finals.The first of them was held in Novi Sad, where Crvena zvezda beat the National Champion Partizan, then the host Vojvodina and, finally, FMP Železnik.All three matches were won in overtime, which is something to remember, especially when it is known that those matches were played without some of the best players, including the team captain Igor Rakočević who missed the final match.