The current trend for substituting synthetic compounds with natural ones in the design and production of functional and healthy foods has increased the research interest about natural colorants. Although coloring agents from plant origin are already used in the food and beverage industry, the market and consumer demands for novel and diverse food products are increasing and new plant sources are explored. Fresh vegetables are considered a good source of such compounds, especially when considering the great color diversity that exists among the various species or even the cultivars within the same species. In the present review we aim to present the most common species of colored vegetables, focusing on leafy and fruit vegetables, as well as on vegetables where other plant parts are commercially used, with special attention to blue color. The compounds that are responsible for the uncommon colors will be also presented and their beneficial health effects and antioxidant properties will be unraveled.