Background: The aim of this analysis was to ascertain the type of relationship between fish and seafood consumption, omega-3 polyunsaturated fatty acids (ω-3 PUFA) intake, and depression prevalence. Methods: Cross-sectional analyses of the PREDIMED-Plus trial. Fish and seafood consumption and ω-3 PUFA intake were assessed through a validated food-frequency questionnaire. Self-reported life-time medical diagnosis of depression or use of antidepressants was considered as outcome. Depressive symptoms were collected by the Beck Depression Inventory-II. Logistic regression models were used to estimate the association between seafood products and ω-3 PUFA consumption and depression. Multiple linear regression models were fitted to assess the association between fish and long-chain (LC) ω-3 PUFA intake and depressive symptoms. Results: Out of 6587 participants, there were 1367 cases of depression. Total seafood consumption was not associated with depression. The odds ratios (ORs) (95% confidence intervals (CIs)) for the 2nd, 3rd, and 4th quintiles of consumption of fatty fish were 0.77 (0.63–0.94), 0.71 (0.58–0.87), and 0.78 (0.64–0.96), respectively, and p for trend = 0.759. Moderate intake of total LC ω-3 PUFA (approximately 0.5–1 g/day) was significantly associated with a lower prevalence of depression. Conclusion: In our study, moderate fish and LC ω-3 PUFA intake, but not high intake, was associated with lower odds of depression suggesting a U-shaped relationship.