Removal of heavy metal ions ($Cd^{2+}$ and $Zn^{2+}$) by electrocoagulation (ECG) was investigated in an acidic condition, which is necessary for re-using or discharging the mediated electrochemical oxidation (MEO) media. Effects of various parameters such as electrolytes, current densities, and electrode materials were examined for a metal-contaminated MEO system using $Fe^{2+}/Fe^{3+}$ pairs as a mediator. It was found that ECG with Al electrodes is greatly affected by the presence of $Fe^{2+}$. [$Cd^{2+}$] and [$Zn^{2+}$] remain constant until [$Fe^{2+}$] reaches a certain concentration level (ca. 10 mM). This preferential removal of $Fe^{2+}$ during ECG with Al electrodes is not alleviated by controlling current densities, potential programs, and solution mixing. ECG with Fe electrodes, on the other hand, resulted in relatively fast removal of $Cd^{2+}$ and $Zn^{2+}$ under coexistence of $Fe^{2+}$, indicative of the different role between $Fe^{n+}$ generated from an electrode and $Fe^{2+}$ initially present in a solution. When ECG was performed with Fe electrodes until [$Fe^{n+}$] became the same as the concentration of initially present $Fe^{2+}$, [$Cd^{2+}$] and [$Zn^{2+}$] were reduced to one-tenth of the initial concentrations, suggesting the possibility of a continuous use of the medium for a subsequent MEO process.