Optically induced ultrafast demagnetization and its recovery in superparamagnetic colloidal iron oxide (Fe3O4) nanocrystals have been investigated via time-resolved Faraday rotation measurements. Optical excitation with near-infrared laser pulse resulted in ultrafast demagnetization in approximately 100 fs via the destruction of ferrimagnetic ordering. The degree of demagnetization increased with the excitation density, and the complete demagnetization reached at approximately 10% excitation density. The magnetization recovered on two time scales, several picoseconds and hundreds of picoseconds, which can be associated with the initial reestablishment of the ferrimagnetic ordering and the electronic relaxation back to the ground state, respectively. The amplitude of the slower recovery component increased with the size of the nanocrystals, suggesting the size-dependent ferrimagnetic ordering throughout the volume of the nanocrystal.