The Cuatro Ciénegas Basin (CCB) in the central part of the Chihuahan desert (Coahuila, Mexico) hosts a wide diversity of microorganisms contained within springs thought to be geomorphological relics of an ancient sea. A major question remaining to be answered is whether bacteria from CCB are ancient marine bacteria that adapted to an oligotrophic system poor in NaCl, rich in sulfates, and with extremely low phosphorus levels (<0.3 microM). Here, we report the complete genome sequence of Bacillus coahuilensis, a sporulating bacterium isolated from the water column of a desiccation lagoon in CCB. At 3.35 Megabases this is the smallest genome sequenced to date of a Bacillus species and provides insights into the origin, evolution, and adaptation of B. coahuilensis to the CCB environment. We propose that the size and complexity of the B. coahuilensis genome reflects the adaptation of an ancient marine bacterium to a novel environment, providing support to a "marine isolation origin hypothesis" that is consistent with the geology of CCB. This genomic adaptation includes the acquisition through horizontal gene transfer of genes involved in phosphorous utilization efficiency and adaptation to high-light environments. The B. coahuilensis genome sequence also revealed important ecological features of the bacterial community in CCB and offers opportunities for a unique glimpse of a microbe-dominated world last seen in the Precambrian.