Invasion success is dependent on the ability of a species to discover and exploit novel food resources. Within this context, individuals must be willing to taste novel foods. They must also be capable of evaluating the nutritional content of new foods, and selecting their relative intake in order to fulfil their nutritional needs. Whereas the former capacity is well studied, little is known about the latter capacity. First, using the common myna as a model avian invader species, we quantified the willingness of mynas to taste novel foods relative to familiar ones. Mynas readily tasted high protein (HP) novel foods and consumed them in higher quantities compared to a familiar food. Data showed that at three different levels – mixes, ingredients and macronutrients – intake could not be explained by a random model. In experiment 2, we confirmed that mynas were making their selection based on protein (P) content rather than a selection for novelty per se. When given the choice of three equally unfamiliar foods, mynas again ate disproportionately from the high protein relative to high lipid and high carbohydrate foods. Analysis revealed that mynas consumed amounts of protein that were closer to the ones in their natural diet. Finally, in experiment 3, we measured inter-individual variation in innovation and exploration propensities, and examined associations with inter-individual variation in consumption of specific macronutrients. This analysis revealed that individuals that selected HP pellets were more exploratory and individuals that selected HC pellets were quicker to solve the innovative foraging task. These findings indicate that not only the willingness to taste novel foods, but also the capacity to evaluate their nutritional content, might be central to the myna's substantial ecological success.