Background: Cardiovascular diseases are caused by multiple behavioral factors, including different dietary factors. We examined to what extent fruit, vegetable and fish consumption are related, and whether behavioral determinants vary across these dietary behaviors from a Transtheoretical model perspective. Methods: Data were collected among 1142 participants (T0; response rate 46%) selected from an Internet panel, who were followed-up one-week later (T1; N = 1055, response rate 92%). Mean age was 35.4 (SD = 11.9) years, 35% was male, and most respondents were of Dutch origin (90%). Of the respondents, 13%, 44% and 43% had a low, medium or high level of education, respectively. Electronic questionnaires assessed fruit, vegetable and fish intake (food frequency questionnaires), stages of change, decisional balance and self-efficacy, for each of these three behaviors. Results: Stages of change and (changes in) fruit, vegetable and fish intake were only weakly associated; decisional balance and self-efficacy were more strongly associated. Some presumed predictors of stage transitions were similar for fruit, vegetable, and fish intake, i.e., strong pros predicted progress out of precontemplators and low self-efficacy predicted relapse from action/maintenance for all behaviors. However, progress out of contemplation and out of preparation showed different patterns for fruit, vegetable and fish intake. Conclusion: The weak associations between intakes and potential determinants for fruit, vegetable, and fish consumption do not warrant an integrated dietary change approach targeting the same determinants for each behavior.