In this study, we investigated the effects of furcellaran–gelatine (FUR/GEL) coatings incorporated with herb extracts on the quality retention of carp fish during refrigeration. Nutmeg, rosemary, thyme, milfoil, marjoram, parsley, turmeric, basil and ginger were subjected to water and ethanol extraction methods (10% concentration of herbs). The water extractions of the rosemary and thyme (5%) were used for the further development of coatings due to their high 2,2-Diphenyl-1-picrylhydrazyl (DPPH: 85.49 and 83.28%) and Ferric Reducing Antioxidant Power Assay values (FRAP: 0.46 and 0.56 mM/L) (p < 0.05), respectively. A new, ready-to-cook product with the coatings (carp fillets) was evaluated regarding quality in terms of colour parameters, texture profile, water activity, Thiobarbituric Acid Reactive Substances (TBARSs) and sensory analyses during 12 days of storage at 4 °C. The results show that the colour of the carp fillets treated with the rosemary and thyme extracts became slightly darker and had a propensity towards redness and yellowness. In contrast to the control group, the carp fillets stored in the coatings with the rosemary extract effectively slowed the lipid oxidation processes. Therefore, the innovative coatings produced from carp processing waste may have high potential as components in convenience food products and could extend the shelf-life of carp fillets during refrigerated storage. However, further research is needed to assess the microbiological stability of the obtained food products.