Searches for dark matter at the LHC have largely focused on Weakly Interacting Massive Particles (WIMPs). But what if instead of just one type of dark matter particle, there exists a richer dark sector hidden from ordinary view? This opens up a whole new paradigm for dark matter searches, allowing us to focus not only on the coupling between dark matter and the Standard Model, but also on the interactions between dark matter constituents themselves. The LHC is in a unique position to investigate such a rich dark sector which is otherwise difficult to probe with direct and indirect detection techniques. In this talk, I will describe a new, ongoing search for dark matter with the CMS detector, using Inelastic Dark Matter (iDM) predictions as a guide. The iDM model offers a unique and striking long-lived final-state signature at the LHC, which can be exploited to access a significant fraction of unexplored dark matter parameter space. I will review the iDM model, describe the main features of the expected signature, and discuss the ongoing efforts at CMS to look for this signal.