A gradient-based shape optimization scheme combined with an interface-enriched generalized finite-element method (IGFEM) is proposed to efficiently optimize electro-magnetic (EM) problems. To avoid mesh distortion or the expensive process of repeatedly creating a conformal mesh for each design configuration, the problem geometry is projected onto a fixed background mesh that is not necessarily conformal to the geometry. The IGFEM, with an enriched solution space in nonconformal elements, is adopted for an accurate EM simulation. An analytical sensitivity analysis is presented to compute the derivatives of the objective and constraint functions. Because of the fixed background mesh, the design velocity field term in the sensitivity analysis is evaluated only at the geometry interfaces, and the efficiency of this method is significantly enhanced. An optimization of the radius of a dielectric cylinder to achieve the desired echo width is presented for verification.