While there is evidence of the factors influencing the healthfulness of consumers' food choice, little is known about how consumers perceive the healthfulness of their shopping. This study aimed to explore consumers' perceptions of, and identify barriers to, conducting a healthful shop. Using a qualitative approach, consisting of an accompanied shop and post-shop telephone interview, 50 grocery shoppers were recruited. Results showed that consumers used three criteria to identify a healthful shop: (1) inclusion of healthful foods; (2) avoidance or restriction of particular foods; and (3) achieving a balance between healthful and unhealthful foods. Those who take a balanced approach employ a more holistic approach to their diet while those who avoid or include specific foods may be setting criteria to purchase only certain types of food. The effectiveness of any of these strategies in improving healthfulness is still unclear and requires further investigation. Two barriers to healthful shopping were: (i) lack of self-efficacy in choosing, preparing and cooking healthful foods and (ii) conflicting needs when satisfying self and others. This highlights the need for interventions targeted at building key food skills and for manufacturers to make healthful choices more appealing.