As a potential candidate for the next generation of high-temperature alloys, refractory high entropy alloys (RHEAs) have excellent mechanical properties and thermal stability, especially for high-temperature applications, where the processing of RHEAs plays a critical role in engineering applications. In this work, the wire electrical discharge machining (WEDM) performance of WNbMoTaZr (x = 0.5, 1) RHEAs was investigated, as compared with tungsten, cemented carbide and industrial pure Zr. The cutting efficiency (CE) of the five materials was significantly dependent on the melting points, while the surface roughness (Ra) was not. For the RHEAs, the CE was significantly affected by the pulse-on time (ON), pulse-off time (OFF) and peak current (IP), while the surface roughness was mainly dependent on the ON and IP. The statistical analyses have shown that the CE data of RHEAs have relatively-smaller Weibull moduli than those for the Ra data, which suggests that the CE of RHEAs can be tuned by optimizing the processing parameters. However, it is challenging to tune the surface roughness of RHEAs by tailoring the processing parameters. Differing from the comparative materials, the WEDMed surfaces of the RHEAs showed dense spherical re-solidified particles at upper recast layers, resulting in larger Ra values. The proportion of the upper recast layers can be estimated by the specific discharge energy (SDE). Following the WEDM, the RHEAs maintained the main BCC1 phase, enriched with the W and Ta elements, while the second BCC2 phase in the Zr1.0 RHEA disappeared. Strategies for achieving a better WEDMed surface quality of RHEAs were also proposed and discussed.