Anthocyanins are polyphenolic O-glycosides widely responsible for the bright red, purple, and blue colors in the plant kingdom, including a great variety of fruits and vegetables. Hence, they have attracted considerable scientific and industrial interest as potential natural food colorings. However, individual anthocyanins are intrinsically reactive molecules combining electrophilic, nucleophilic, and electron-donating properties. This reactivity may be not only a source of color diversity with, for instance, the formation of new pigments upon winemaking and storage but also a cause of great color instability involving a combination of reversible and irreversible mechanisms (e.g., water addition, autoxidation) leading to colorless products. Hence, using anthocyaninrich plant extracts as food colorings requires a deep understanding of these color-damaging mechanisms and, no less importantly, of the color-stabilizing mechanisms developed by plants, including π-stacking interactions (self-association, copigmentation), metal binding, and a combination of both. The potential of anthocyanins from deeply colored vegetables, typically acylated by hydroxycinnamic acid residues, will be emphasized in that respect. Moreover, food-grade biopolymers (proteins, polysaccharides) may provide suitable matrices for ready-to-use formulations of anthocyanins as food colorings. In this short review, the mechanisms of color loss and color stabilization are discussed as a function of anthocyanin structure and environment, and some challenges still ahead are outlined.