We present a novel method for 3-D optical data storage that has submicron-size resolution, provides a large contrast in index of refraction, and is applicable to a wide range of transparent materials. Bits are recorded by focusing 100-fs laser pulses inside the material using a 0.65 NA objective. The laser pulse produces a submicron-diameter structurally altered region with high contrast in index of refraction. Binary information can be recorded by writing such bits in multiple planes, and read out with a microscope objective with a short depth of field. We demonstrate data storage and retrieval with 2-m in-plane bit spacing and 15-m inter-plane spacing (17 Gbits/cm3). Scanning electron microscopy and atomic force microscopy show structural changes confined to an area 200 nm in diameter.