Bacteria of the deeply branching phylum Verrucomicrobia are rarely cultured yet commonly detected in metagenomic libraries from aquatic, terrestrial, and intestinal environments. We have sequenced the genome of Opitutus terrae PB90-1, a fermentative anaerobe within this phylum, isolated from rice paddy soil and capable of propionate production from plant-derived polysaccharides.