A unique, previously undescribed Gram-negative bacterium was isolated from several soils in Texas and extensively characterized in this study. The cells measured 1-2 by 4-6 μm. The distinguishing characteristic of the bacterium is the extraordinary capsular material which surrounds the cells. The new isolates are aerobic, mesophilic, non motile and have the ability to utilize a variety of organic compounds as the sole source of carbon and energy. The organism grows optimally at 30° C and the optimal pH lies between 7.0-8.0. The isolates produce catalase but oxidase is not produced. They do not produce indole or hydrogen sulfide. The organism can hydrolyze gelatin and Tween 80 but not starch, esculin and casein. The major cellular fatty acid is anteiso 15:0. The guanine and cytosine content is 58-62 mole%. The organism's taxonomic position was further established by specific gene probes, 16S rRNA homology, DNA homology and "ribotyping." These data showed that it was most closely related to members of the genus Paenibacillus, although somewhat divergent from other species classified in this genus. After careful evaluation of the results obtained during this study, it is proposed that this unique bacterium be named Paenibacillus velasolus sp. nov.