The analysis of fatigue behavior of bituminous binders is a complex issue due to several time-temperature dependent phenomena which interact simultaneously, such as damage accumulation, viscoelasticity, thixotropy, and healing. The present research involves rheological measurements aimed at evaluating the fatigue behavior and compares the self-healing capability of two plain bitumen and a bio-binder obtained by partially replacing one of the plain bitumen with a renewable bio-oil. Healing potential was assessed by means of an experimental approach previously implemented for modified bitumen and bituminous mastic and based on the use of a dynamic shear rheometer (DSR). The effects of some variables such as bitumen type, bio-oil addition, and aging on the healing potential of binders were taken into account. Results showed that the above-mentioned method for healing analysis is also suitable for conventional and bio-add binders. Outcomes of the experimental investigation highlight that fatigue and self-healing are mainly dependent on binder consistency and also affected by aging. Finally, the addition of bio-oil may induce even better performances in terms of healing potential compared to conventional bitumen, especially in aged condition.