Refractory high-entropy alloys (RHEAs) are categorized as difficult-to-machine materials due to their excellent mechanical properties. Electrical discharge machining (EDM) is a special processing method for RHEAs, which faces challenges such as low machining efficiency. In this work, electrochemical discharge machining (ECDM) was proposed for (TiVZrTaW)_99.5N_0.5 and (TiVZrTa)W₅ (at. %, denoted as W20N0.5 and W5, respectively) RHEAs, and their machining performances were investigated and compared with EDM. At a peak current of 25 A, the material removal rate (MRR) using ECDM is more than twice that of EDM for W20N0.5 (reaching to 1.24 mm³/min) and 1.5 times higher than that for W5. Both W20N0.5 and W5 RHEAs exhibited higher MRR in ECDM based on the analyses of the influence of top diameter, bottom diameter, machining depth, and surface roughness (Ra). The process and mechanisms of material removal were examined through the microstructural morphology and elemental distribution analyses. This work proposed a more effective route for machining RHEAs by ECDM compared to the conventional EDM.