Cellulosilyticum lentocellum DSM 5427 is an anaerobic, endospore-forming member of the Firmicutes. We describe the complete genome sequence of this cellulose-degrading bacterium, which was originally isolated from estuarine sediment of a river that received both domestic and paper mill waste. Comparative genomics of cellulolytic clostridia will provide insight into factors that influence degradation rates.