We present a method for fabricating high aspect ratio metal-oxide, sub-wavelength grating structures. These "nano-hair" structures are composed of alumina cylindrical pillars, partially embedded in a supporting fused silica substrate. The fabricated nano-hair structures demonstrate phase control of the transmitted beam while maintaining a peak transmitted power greater than 93% around a central wavelength of λ(o) = 1.55 µm. Based on this principle, discrete and continuous phase functions can be encoded by controlling the lithographic process.