Health messages framed to be congruent with people’s motivational orientation have been shown to be generally effective in promoting health behavior change, but some inconsistencies have been found. This study tested whether the perceived quality of a health message moderated the congruency effect in the domain of fruit and vegetable (FV) consumption. Undergraduate participants (N = 109) read a health message promoting FV intake in which the frame (gain vs. loss) was either congruent or incongruent with their approach/avoidance motivational orientation. Perceived message quality and intention to increase FV intake were assessed after message exposure, and self-reported FV intake was assessed one week later. A significant interaction between congruency and perceived message quality was found on both intention and FV intake. When messages were congruent, higher intentions and FV intake were observed when perceived message quality was high, but the reverse pattern was observed when perceived message quality was low. The findings support the potential utility of using congruently-framed messages to promote fruit and vegetable consumption, while also underscoring the necessity of using high-quality messages in order for congruency to influence health-related behaviors.