The rising pollution by synthetic dyes from the textile industry is a serious health problem calling for safer chemicals and textile production methods. As an alternative, bio-based colorants are increasingly used for food, cosmetics, flavors, medical applications. Here we review bio-based textile dyeing with focus on dye classification, methods to improve dyeing, and mordants and bio-mordants. Dyes are classified according to their origin such as plant, animal, mineral, microbes, and waste; their chemical structure, e.g., indigoid, flavonoid, and tannin dyes; their color; and their application such as mordant dyes and direct dyes. Methods to improve dyeing include sonication, plasma, ultraviolet, microwave, and gamma irradiation. Most bio-based dyes are biodegradable, renewable, non-hazardous, non-allergic, and simple to use. Yet bio-based dyes are limited by poor color fastness and a constrained palette of shades. These limitations can be resolved by using mordants on textile materials. Bio-mordants enhance the bonding of natural dyes to the fabric, resulting in textiles that exhibit excellent washing fastness.