Microbiological calcium carbonate precipitation (MCP) has been investigated for its ability to improve the compressive strength of concrete mortar. However, very few studies have been conducted on the use of calcite-forming bacteria (CFB) to improve compressive strength. In this study, we discovered new bacterial genera that are capable of improving the compressive strength of concrete mortar. We isolated 4 CFB from 7 environmental concrete structures. Using sequence analysis of the 16S rRNA genes, the CFB could be partially identified as Sporosarcina soli KNUC401, Bacillus massiliensis KNUC402, Arthrobacter crystallopoietes KNUC403, and Lysinibacillus fusiformis KNUC404. Crystal aggregates were apparent in the bacterial colonies grown on an agar medium. Stereomicroscopy, scanning electron microscopy, and x-ray diffraction analyses illustrated both the crystal growth and the crystalline structure of the CaCO3 crystals. We used the isolates to improve the compressive strength of concrete mortar cubes and found that KNUC403 offered the best improvement in compressive strength.