Purpose: This study investigates the association between seafood consumption and frailty according to gender in the Korean elderly. Methods: Cross-sectional data from the Seventh (2016–2018) Korea National Health and Nutrition Examination Survey was procured for this study. Data from 3,675 subjects (1,643 men and 2,032 women) aged ≥ 65 years were analyzed. Levels of seafood intake were assessed by a one-day 24-hour dietary recall, and subjects were classified into three tertiles by gender according to frailty phenotype: robust, pre-frail, and frail. Multinomial logistic regression analysis was performed to clarify the association between seafood consumption and frailty for each gender. Results: The prevalence of frailty was determined as 13.4% for men and 29.7% for women. Participants with a higher seafood intake had higher intakes of grains, fruits, and vegetables, while the intake of meat was significantly lower. In both men and women, the group with higher seafood intake showed higher energy and micronutrient intakes. The frail prevalence and frailty score were significantly low in the highest tertiles of seafood consumption compared to the lowest tertile in men and women (p < 0.001). After adjusting for confounder, the highest tertile of seafood consumption showed a decreased risk of frailty compared to the lowest tertile only in women (hazard ratio [HR], 0.50; 95% confidence interval [CI], 0.32–0.78; p-trend = 0.008 vs. HR, 0.52; 95% CI, 0.32–0.83; p-trend = 0.008;respectively). Conclusion Results of this study suggest that seafood consumption potentially decreases the risk of frailty in the elderly.