The European Commission is proposing new directives to support the sustainable management of textile waste across the EU. For that, new solutions for textile waste (TW) valorisation are needed, along with alternatives to fossil-based products in textile finishing processes. In this work, innovative bio-based coatings were developed by incorporating TW to confer colour and aesthetic properties and bacterial cellulose (BC) as a sustainable alternative to fossil-based commercial polymers. The developed coatings presented a soft touch, no breaks and excellent flexibility. The variation in the thickness of each layer enabled the creation of coatings with different colour shades and textures. The diverse colour palette, the excellent flexibility, and the ability to join the coatings using conventional sewing methods, make the developed coatings suitable for various applications in the field of textiles, footwear, and decoration. Moreover, quality control parameters required in textile industry regarding durability and light fastness were accomplished. The best results were reached with the mixture of 3 g of green TW and 1 g black TW at a thickness of 0.4 mm, attaining a grey-scale rating of 4–5 in both tests. The developed work demonstrates an innovative approach in which the addition of BC and TW allowed reduce the synthetic components of a conventional coating. A new approach to confer colour to coatings without adding synthetic pigments was also validated.