Fruit and vegetables contain molecules that have particular colors, which can potentially be an environmentally attractive substitute for their synthetic counterparts in (non )food applications. The most sustainable source for such natural colorants would be by the valorization of by-products from the fruit and vegetable industries, but qualitative and quantitative characteristics of food by-products for this purpose remain scarce. Natural dyes also show mediocre stability and affinity toward textile fibers, which questions their potential feasibility for application and level of sustainability to overcome these issues. This review describes three dye classes (i.e., anthocyanins, quinones, and carotenoids) along with their occurrence, mass, and concentration in by-products that are generated from agricultural losses as well as the fruit and vegetable processing industries. To tackle the shortcomings of natural dyes on fibers, several application techniques were collected from the literature. A discussion on techno-economic potential and environmental sustainability is included. The latter is done by including a life cycle assessment (LCA) to investigate the environmental impact of extracting anthocyanins, quinones, and carotenoids from fruit and vegetable processing by-products and their subsequent application to the dyeing process. The mapping of by-products for each natural dye class illustrates the vast availability of agro-food residues (>0.1 Mt annually in the EU-28) with a natural dye content of up to 56 kg/t DW for anthocyanins, 18 kg/t DW for quinones, and 593 kg/t DW for carotenoids. Metallic mordants are mostly favored for improving the fixation of natural dyes but entail potential environmental issues. Greener approaches, such as biomordants and enzymes, still show room for improvement, chemical modification methods might also guarantee dye fixation, though questionable in environmental sustainability. The different valorization scenarios of anthocyanins, quinones, and carotenoids from food waste, analyzed with LCA, showed the environmental competitiveness of these natural dyes, applied as a crude extract, compared to synthetic dyes. The valorization routes design shows that agricultural losses and food processing waste streams are adequate sources of natural dyes, especially to be applied in niche scale applications.