In one embodiment, a holographic data storage medium includes a substrate, a holographic recording material, and an optically detectable tracking pattern on the medium. The substrate may have first and second substrate portions. The holographic recording material may be a photopolymer, and the medium may have a sandwiched construction, where the holographic recording material is sandwiched between the first and second substrate portions. The optically detectable tracking pattern may be replicated on at least one of the substrate portions. Alternatively, the optically detectable tracking pattern may be recorded as a holographic grating in the holographic recording material. The tracking pattern may facilitate the ability to pinpoint the location of the holographic bit maps on the holographic medium to within a fraction of a micron.