Synthetic industrial wastewater samples containing mercury (Hg), arsenic (As), and lead (Pb) ions in various concentrations were prepared and treated by air gap membrane distillation (AGMD), a promising method for heavy metals removal. Three different membrane pore sizes (0.2, 0.45, and 1 μm) which are commercially available (TF200, TF450, and TF1000) were tested to assess their effectiveness in combination with various heavy metal concentrations and operating parameters (flow rate 1–5 L/min, feed temperature 40–70 °C, and pH 2–11). The results indicated that a high removal efficiency of the heavy metals was achieved by AGMD. TF200 and TF450 showed excellent membrane removal efficiency, which was above 96% for heavy metal ions in a wide range of concentrations. In addition, there was no significant influence of the pH value on the metal removal efficiency. Energy consumption was monitored at different membrane pore sizes and was found to be almost independent of membrane pore size and metal type.