The addition of fibers to cementitious composites can provide improved ductility, energy dissipation, and resistance to cracking. However, it is also important to minimize residual deformations and provide crack-closing capabilities when the material is subjected to cyclic loading. In this study, the behavior of mortar mixtures with randomly distributed superelastic shape memory alloy fibers was investigated. Superelastic shape memory alloys are metallic alloys that possess unique characteristics such as the ability to undergo large deformations, excellent re-centering ability, and good energy dissipation capacity. To study the impact of shape memory alloys as a viable alternative to conventional fiber-reinforced cementitious composites, shape memory alloy fiber–reinforced mortar beam specimens with varying fiber volume fractions were prepared and tested under cyclic flexural loading. Digital image correlation method was used to measure full-field deformations and monitor the damage evolution on the surface of the specimens. Test results were analyzed in terms of flexural strength capacity, mid-span deflection, crack width, fiber distribution, and re-centering and crack recovery ratios for each specimen. Results indicate that the addition of shape memory alloy fibers to mortar composites can enhance flexural strength and ductility while providing re-centering and crack recovery capabilities at large deformation levels.