We report the design and fabrication of nanostructured gradient index microaxicons suitable for integration with optical fibers. A structure with the effective refractive index decreasing linearly from the center to the edges (i.e., an axicon) was designed using a combination of a simulated annealing method and the effective medium theory. The design was verified numerically with beam propagation method simulations. The axicons were made by the modified stack and draw method and integrated with optical fibers. The optical properties of the fabricated elements were measured and showed good agreement with the numerical simulations. The fabricated axicons produced an extended line focus at a distance from about 70 to 160 μm from the lens facet with a minimum FWHM diameter of 8 μm at 90 μm. At smaller distances, an interference pattern is observed both in the experiment and in simulations, which is attributed to the uneven effective refractive index profile at the structure.