The atomic pair distribution function (PDF) analysis of X-ray powder diffraction data has been used to study the structure of small and ultra-small CdSe nanoparticles. A method is described that uses a wurtzite and zinc-blende mixed phase model to account for stacking faults in CdSe particles. The mixed-phase model successfully describes the structure of nanoparticles larger than 2 nm yielding a stacking fault density of about 30%. However, for ultrasmall nanoparticles smaller than 2 nm, the models cannot fit the experimental PDF showing that the structure is significantly modified from that of larger particles and the bulk. The observation of a significant change in the average structure at ultra-small size is likely to explain the unusual properties of the ultrasmall particles such as their white light emitting ability.