Soil improvement using bio-engineering approaches such as microbial-induced calcite precipitation (MICP) has been encouraged in recent years for engineering applications such as stabilization of soil slopes and soil erosion mitigation in place of traditional methods such as cement grouting. Bio-cementation in MICP-treated soils is greatly affected by the composition of the treatment solutions, treatment sequences (TS), and treatment duration, which consequently affects the homogeneity in the precipitation patterns of the calcium carbonate in soil and soil engineering properties. To address this, seven different treatment sequences (TS 1–TS 7) using different constituents, namely, bacterial culture, urea, calcium chloride dihydrate, sodium bicarbonate, ammonium chloride, and nutrient broth for soil treatment are compared in this study. The treatment sequences were classed into one-phase of treatment and two-phase of treatment. The solutions added in the 3rd step of each treatment sequence had different compositions. The surface percolation method was adopted for soil treatment for a 14-day period. An isolated ureolytic bacterium, Cytobacillus sp., was used to achieve bio-cementation in soil. The treated soil samples were subjected to unconfined compressive strength (UCS) and acid-washing tests to evaluate the strength characteristics and calcium carbonate precipitation. The test results demonstrated that significantly higher strength values were achieved in soil samples following TS 4, TS 5, TS 6, and TS 7 sequences compared to the other treatment sequences after 14 days of treatment. Moreover, sequences TS 4 and TS 6 demonstrated outperforming strength characteristics due to a high rate of hydrolysis and CaCO3 precipitation, which was validated by pH readings and dry density measurements, respectively. The formation of dense and higher precipitation of CaCO3 crystals in these treatment sequences was confirmed through microscopic examination.