The process of soil stabilization involves enhancing the engineering properties of soil by altering it using physical or chemical means, thus improving its strength, bearing capacity, durability, etc. In this paper, an attempt is done to stabilize the locally available soil to be used for pavements, by randomly distributing palmyra fiber. Lime powder also was added to maintain the required consistency limits and to control the swelling behavior of the stabilized soil. Short palmyra fibers were used by maintaining the same aspect ratio, but the fiber contents were varied between 0.25 and 1.00% of the soil weight. It is observed that about 6% lime is required to control the Atterberg limits, and the same is effective in reducing the swelling behavior of the soil. The inclusion of randomly distributed palmyra fiber into the soil–lime mixture has generally improved the properties, including unconfined compressive strength and California bearing ratio. The mixture combinations were subjected to wet-dry durability cycles, and the addition of lime powder and palmyra fiber was observed to improve the durability. However, none of the tested combination could pass the durability test criteria. From the study, it is concluded that the palmyra fiber in short length can be randomly distributed in soil to improve its properties, with lime powder (if issues related swelling or consistency limits exist).