Background: Gaps remain on the safety of egg intake on cardiovascular health, setting the study’s aim to investigate the association between quantity and frequency of egg consumption, with established dyslipidemia. Methods: Study participants (N = 3558, 40.3% males) included individuals from the Hellenic National and Nutrition Health Survey (HNNHS), of national representation. Quantity and frequency of egg consumption was determined. Minimally adjusted, multivariable logistic and linear analysis were used to assess egg consumption and dyslipidemia. Results: The more frequent egg consumption compared to no or rare egg consumption significantly decreased the odds of dyslipidemia in the minimally adjusted (Odds Ratio (OR) for frequency: 0.83; 95% Confidence Interval (CI): 0.752, 0.904; OR for quantified frequency: 0.87; 95% CI: 0.796, 0.963) and the fully adjusted models (OR for frequency: 0.80; 95% CI: 0.718, 0.887; OR for quantified frequency: 0.85; 95%CI: 0.759, 0.945). Level of serum cholesterol and LDL-c were significantly lower with higher frequency and quantified frequency of egg consumption in all models. Conclusion: Eggs do not increase the risk of dyslipidemia and can be consumed as part of a healthy diet that is high in fiber and low in saturated fat, without excessive energy intake, by all individuals.