We introduce a new method for microstructural shape optimization of heterogeneous structural materials. The proposed gradient-based shape optimization scheme, which is based on a NURBS-based Interface-enriched Generalized Finite Element Method (NIGFEM), relies on the stationary nature of meshes that do not conform to the material interfaces that define the microstructure, thereby avoiding mesh distortion issues that plague conventional finite-element-based shape optimization studies. The NIGFEM provides three major benefits. Firstly, by relying on simple structured meshes that do not conform to the complex microstructure of the heterogeneous media, the NIGFEM significantly reduces the complexity of the mesh generation steps during the optimization process. Secondly, the finite element approximation space used in the NIGFEM is augmented with Non-Uniform Rational B-Splines (NURBS) that allows for the capture of the weak discontinuity present along curvilinear material interfaces. Finally, in the NIGFEM-based adjoint shape sensitivity approach adopted in this work, only the enrichment (interface) nodes move, appear or disappear during the shape optimization process. To demonstrate the performance of the method, a set of microstructural shape optimization problems for the linear and nonlinear design of heterogeneous particulate composites are presented.