Controlled low-strength material (CLSM) is a flowable, self-leveling backfill material used as an alternative to compacted soil for backfilling trenches, retaining walls, underground cavities, and in pavement construction. This study aims to investigate the permanent deformation of CLSM reinforced with basalt fibers. Basalt fibers with lengths of 6 and 24 mm are incorporated into CLSM mixtures to assess their impact on flowability, setting times, and mechanical properties. Mechanical testing indicates that longer fibers improve tensile strength through a bridging effect. Repeated load triaxial tests are conducted to evaluate the permanent strain behavior under repeated loading. The results show that permanent strain increases with the deviator stress and number of loading cycles. A regression model accounting for the number of loading cycles and deviator stress provides accurate permanent-strain predictions, and the permanent strain behaviors are classified based on the refined shakedown theory. Therefore, the basalt-fiber-reinforced CLSM suggested in this study may be suitable for pavement base material due to its relatively low permanent strain under typical stress conditions.