The Large Hadron Collider has extended the reach of particle-physics experiments by more than a factor of three, with a potential for discovery of new physics at the TeV scale. Many models of physics beyond the Standard Model predict new, massive particles with long lifetimes. Examples include supersymmetry with R-parity violation, suppressed decays of the next-to-lightest supersymmetric particle, or models with hidden sectors. The decay vertices of particles with lifetimes of order 10 ps to 10 ns can be efficiently identified by the ATLAS detector. We describe progress on the search for such particles, including methods for reconstruction and background suppression and the expected sensitivity of the search.