The performance of styrene-butadiene-styrene (SBS) modified asphalt mixtures can be further improved by adding a variety of fibers available. Addition of fibers provides a cost-effective solution against increasing the dosage of SBS modified asphalt mixtures. Therefore, in this research three different types of fibers—basalt fiber, polyester fiber and lignin fiber—were added to SBS-7% bitumen binder and their performance was compared with SBS-7% mixture without any fibers. The performance was compared using laboratory tests, including indirect tensile strength tests and dynamic shear rheometer. Indirect tensile strength of all the mixtures was evaluated at various loading rates from 10 MPa/s to 70 MPa/s. Furthermore, stiffness moduli of mixtures were evaluated at frequency rages of 5 Hz, 3.5 Hz, 1.9 Hz and 1.2 Hz. Finite element simulations were conducted using the Burger’s logit model, and microstrain analysis was performed to evaluate rutting and fatigue damage. The results show increased performance in terms of gained tensile strength and complex shear modulus for fiber-modified mixtures. Among the fiber-modified mixtures, basalt fiber outperforms other mixtures. PF and LF exhibit almost similar performances. Basalt fiber mixture outperforms the SBS-7% mixture by 25% and 28% in terms of rutting and fatigue damage, respectively.