Positron lifetimes in nanocrystalline niobium were measured over the grain size range from 35 nm down to 5 nm. Two lifetimes were obtained indicating distinct annihilation sites at the grain surfaces and in the intercrystalline region. X-ray diffraction studies had indicated a bcc to fcc transformation and a concomitant lattice expansion. Positron lifetimes drastically varied below a grain size of 10 nm, coinciding with a sharp increase in the excess free volume of atoms at the grain boundaries as revealed in a model analysis. Doppler broadening measurements also indicated a redistribution of electron momentum, implying a restructuring of the grain surfaces. The occurrence of bcc to fcc transformation is also observed in binary Nb-Al and ternary Al-Nb-Cu alloys.