We report the first observation of the formation of novel Co-based three-dimensional (3D) self-assembly hollow nanostructures, i.e., nest-shaped nanospheres composed of sheet-like particles, via reduction of cobalt salt with sodium tetrahydroboride in cetyltrimethylammonium bromide (CTAB)-cyclohexane-NH4F aqueous solutions. It was found that the cyclohexane has a significant influence on the formation of the nest-shaped Co-based nanospheres, because when the experiments are carried out in the absence of cyclohexane, only sheet-like particles are formed. NH4F plays also an important role in the formation of the hollow nanostructures because without this salt mainly solid spherical structures, composed of sheet-like particles, instead of nest-shaped structures are obtained. The nanostructures are mainly formed by Co, but also a minor amount (17%) of Co2B is present in the final compounds. The structures are characterized by X-ray diffraction (XRD), energy dispersive spectroscopy (EDS), transmission electron microscopy (TEM), high resolution transmission electron microscopy (HRTEM), and field-emission scanning electron microscopy (FESEM). A possible mechanism for the formation of the novel Co-based nanostructures is proposed.