Vegetable consumption in adolescents is reported to be low, at least in part, due to the unappealing sensory properties of vegetables, such as bitter tastes. However, not all vegetables have unappealing sensory properties, and strategies to improve vegetable consumption may benefit from wider consideration. This work aimed to understand the individual characteristics in adolescents from four European countries associated with the regular consumption and liking of vegetables with more appealing and less appealing sensory properties. Adolescents from Denmark (N = 178), the UK (N = 155), France (N = 206) and Italy (N = 197) completed self-report questionnaires to assess all variables. We found higher self-reported consumption and liking of vegetables with more appealing than less appealing sensory properties. Regular consumption of both types of vegetable was associated with healthier eating habits and a higher liking for each vegetable type. Liking for vegetables with more appealing sensory properties was higher in individuals with lower food neophobia, healthier eating habits, higher interest in consuming foods for sensory reasons and higher liking for vegetables with less appealing properties. Liking for vegetables with less appealing sensory properties was higher in individuals with lower food neophobia, higher concern for the consumption of natural foods, and higher liking for vegetables with more appealing properties. Some gender and country-specific differences were also found. Our findings suggest that strategies to increase vegetable consumption in adolescents should focus on increasing healthy eating in general, increasing vegetable liking, and may benefit from reducing food neophobia and enhancing the positive sensory and natural aspects of vegetables.