Despite their importance as a biofuel production platform, only a very limited number of butanol-tolerant bacteria have been identified thus far. Here, we extensively explored butanol- and isobutanol-tolerant bacteria from various environmental samples. A total of 16 aerobic and anaerobic bacteria that could tolerate greater than 2.0% (vol/vol) butanol and isobutanol were isolated. A 16S rRNA gene sequencing analysis revealed that the isolates were phylogenetically distributed over at least nine genera: Bacillus, Lysinibacillus, Rummeliibacillus, Brevibacillus, Coprothermobacter, Caloribacterium, Enterococcus, Hydrogenoanaerobacterium, and Cellulosimicrobium, within the phyla Firmicutes and Actinobacteria. Ten of the isolates were phylogenetically distinct from previously identified butanol-tolerant bacteria. Two relatively highly butanol-tolerant strains CM4A (aerobe) and GK12 (obligate anaerobe) were characterized further. Both strains changed their membrane fatty acid composition in response to butanol exposure, i.e., CM4A and GK12 exhibited increased saturated and cyclopropane fatty acids (CFAs) and long-chain fatty acids, respectively, which may serve to maintain membrane fluidity. The gene (cfa) encoding CFA synthase was cloned from strain CM4A and expressed in Escherichia coli. The recombinant E. coli showed relatively higher butanol and isobutanol tolerance than E. coli without the cfa gene, suggesting that cfa can confer solvent tolerance. The exposure of strain GK12 to butanol by consecutive passages even enhanced the growth rate, indicating that yet-unknown mechanisms may also contribute to solvent tolerance. Taken together, the results demonstrate that a wide variety of butanol- and isobutanol-tolerant bacteria that can grow in 2.0% butanol exist in the environment and have various strategies to maintain structural integrity against detrimental solvents.