Building blocks extracted from natural lateritic soil strata have wide popularity in masonry construction in the state of Kerala in India. However, extensive variations in strength and physical properties can be observed in these blocks even though they are collected from the same location. Stabilized soil blocks from this lateritic soil can be a sustainable solution for standardization. This research aims at optimizing the soil gradation and assessing the significance of clay minerals for the strength characteristics of stabilized earthen building blocks from lateritic soil. Lateritic soil samples from four different locations and depths were collected and tested for their characterization, as well as chemical and mineralogical investigations. The suitability of stabilizers such as cement, lime, and quarry waste was investigated and stabilized lateritic building blocks were manufactured in different particle combinations from each soil sample and tested to study the influences of gradation patterns on stabilization. The best combinations were further investigated for optimization studies. Combined effects of soil gradation, as well as the presence of chemical and mineral contents in the lateritic soil, were found to contribute toward strength gain. Results of the studies reveal the significance of silt content among the particles and the influence of kaolinite and hematite minerals in the soil samples on the strength gain of stabilized laterite blocks.