Generic extensions of the Standard Model that respect baryon and lepton numbers have accidentally stable particles. Typical examples are the lightest exotic neutral fermion, or "neutralino," and fields with nontrivial lepton and baryon charges. In this paper we identify the accidentally stable neutralino with the dark matter, and discuss its phenomenology in the framework of warped extra dimensions. We find that annihilation into other Kaluza-Klein resonances is often allowed and very efficient. The observed dark matter abundance may then be obtained with couplings of order unity and a compactification scale above the TeV. Light dark matter is also possible in the presence of unsuppressed couplings to the Higgs boson. In this latter case dark matter direct detection experiments will soon be able to probe a significant portion of the parameter space. This analysis suggests that dark matter is a natural feature of realistic models with warped extra dimensions.