RK Vardar was founded in 1961, as part of the Vardar Sports Club in Skopje, which had been founded in 1947. The handball team did not have much of a role in the former Yugoslavia, but rose to power in the late 1990s becoming one of three clubs (RK Metalurg and RK Pelister being the others) to dominate the Macedonian handball scene after the independence of the country. They have participated in the EHF Champions League five times and made it to the semifinals of the Cup Winner's Cup three times. Except for 2005, when they came in 4th place, the club has achieved either championship or runner-up in the Macedonian Super League during the past decade since 1999. They achieved a record winner of the Macedonian handball championship by winning their seventh title in 2009 and are the recent record cup winner also with seven. On 15 April 2012, Vardar defeated Metalurg at the Zagreb Arena to become the first SEHA League champion.
Unlike the usual situation in handball of clubs renting halls from municipalities or private owners, RK Vardar itself is the owner of the SRC Kale Sports Hall they play all their home matches in. The capacity of the Arena was expanded to 2.500 seats in 2008. The club plays the EHF Velux Champions League matches in the Sports Center Boris Trajkovski in Skopje. The capacity of the arena is 6.000 seats.