A high prevalence of dental fluorosis has been identified among children in the Gaza Strip. This study aimed to determine the history of breastfeeding and dietary behaviours among children in the Gaza Strip and to examine potential associations with the prevalence and severity of dental fluorosis. A cross-sectional study recruited a stratified cluster random sample of 350 children aged 12–18 years and their mothers. Data about dietary behaviours in the first 7 years of life were collected by interview questionnaire. Dental fluorosis was determined using the Thyllstrup-Fejerskov index. A majority of children were breastfed exclusively in the first 6 months (82.9%) but 98.1% were given tea in the first year of life. The prevalence of dental fluorosis was 78.0%. Both intake of animal proteins and plant proteins were negatively associated with the prevalence and severity of dental fluorosis. Further studies to investigate fluoride intake is required to plan preventive interventions.