This review presents a comprehensive update on the state-of-the-art of nanometer-sized materials in solid-phase extraction (SPE) of trace elements followed by atomic-spectrometry detection. Zero-dimensional nanomaterials (fullerene), one-dimensional nanomaterials (carbon nanotubes, inorganic nanotubes, and nanowires), two-dimensional nanomaterials (nanofibers), and three-dimensional nanomaterials (nanoparticles, mesoporous nanoparticles, magnetic nanoparticles, and dendrimers) for SPE are discussed, with their application for trace-element analysis and their speciation in different matrices. A variety of other novel SPE sorbents, including restricted-access sorbents, ion-imprinted polymers, and metal-organic frameworks, are also discussed, although their applications in trace-element analysis are relatively scarce so far.