Gaussian beam propagation through a novel high refractive index contrast nanostructured Gradient-Index (GRIN) microlens with an arbitrary refractive index distribution is investigated. The concept of the nanostructured GRIN microlenses is based on the effective medium theory and we show numerically, using the FDTD method, that nanostructured GRIN microlenses can focus Gaussian beams in an identical manner to conventional GRIN microlenses. Nanostructured GRIN microlenses have a reduced thickness by almost two orders of magnitude compared to conventional GRIN lenses. We also investigate the accuracy of the standard scalar and paraxial GRIN theory in the case of a very high contrast nanostructured GRIN microlens. The paraxial GRIN lens theory is shown only to give an approximate description of Gaussian beam propagation in such a high contrast nanostructured GRIN microlens.