Background: Balancing work and family demands is often a challenge. Family and job responsibilities may affect many aspects of health, and sleep is an important issue. Work-family conflict (WFC) refers to situations where it is difficult to reconcile family and professional demands. WFC can act in two directions: work-to-family conflicts occur when job demands interfere in family life; family-to-work conflicts arise when family demands interfere with job performance. This study evaluated whether dimensions of WFC—time- and strain-related, work-to-family conflict; family-to-work conflict; and lack of time for self-care and leisure due to work and family demands—were cross-sectionally and longitudinally associated with sleep complaints, by gender. Methods: The sample comprised 9,704 active workers (5,057 women and 4,647 men) from the Brazilian Longitudinal Study of Adult Health (ELSA-Brasil). Standardized questionnaires were used to collect data. WFC was measured at baseline (2008–2010), and sleep complaints were measured at baseline and approximately 4 years after the first visit (2012–2014). To test the association between the four WFC dimensions and sleep complaints, crude and multiple logistic regressions were conducted to estimate odds ratios and 95% confidence intervals. The adjusted model included age, education, marital status, hours worked and work schedule. Results: Mean age at baseline was 48.2 years. Most participants were educated to University degree level (54.5%), married (68.2%) and worked ≤40 h/week (66.1%). At baseline, 48.3% of women and 41.1% of men reported sleep complaints. Frequent WFC was reported by women and men, respectively, as follows: time-related work-to-family conflict (32.6 and 26.1%), strain-related work-to-family conflict (25.3 and 16.0%), family-to-work conflict (6.6 and 7.6%) and lack of time for self-care (35.2 and 24.7%). For both women and men, time- and strain-related work-to-family conflicts and conflicts for lack of time for self-care were cross-sectionally and longitudinally associated with sleep complaints. The findings also suggest a weaker and non-significant association between family-to-work conflict and sleep complaints. Conclusions: The statistically significant associations observed here underline the importance of reducing WFC. In the modern world, both WFC and sleep problems are increasingly recognized as frequent problems that often lead to ill health, thus posing a public health challenge.