We report the first observation of a striking history dependence of the structure function of vortex matter in the peak effect regime in a Nb single crystal by using small angle neutron scattering combined with in situ magnetic susceptibility measurements. Metastable phases of vortex matter, supercooled vortex liquid and superheated vortex solid, have been identified. We interpret our results as direct structural evidence for a first-order vortex solid-liquid transition at the peak effect.