Early introduction of complementary foods can have a detrimental impact on children's long-term health. This study examined the timing and determinants of early introduction of core and discretionary foods among infants in Sydney, Australia. Mothers ( = 1035) from an ongoing population-based birth cohort study were interviewed at 8, 17, 34 and 52 weeks postpartum. The outcome was 'age at which particular core and discretionary food items were first introduced'. Multivariable logistic regression models were used to investigate family and infant-related determinants of early introduction of core (<17 weeks of age) and discretionary foods (<52 weeks of age). Of the 934 mother-infant dyads interviewed, 12% ( = 113) of infants were introduced core foods before 17 weeks of age (median: 22). Mothers working part-time (adjusted odds ratio (OR): 3.42, 95% confidence interval (CI): 1.54-7.62) and those exclusively formula-feeding their babies at four-weeks postpartum (adjusted OR 3.26, 95% CI: 1.99-5.33) were most likely to introduce core foods early. Ninety-five percent ( = 858) of infants were introduced discretionary foods before 52 weeks of age (median: 28). Low socio-economic status was significantly associated with early introduction of discretionary foods (adjusted OR: 3.72, 95% CI: 1.17-11.78). Compliance with infant feeding guidelines related to core foods was better; however, discretionary foods were introduced early in most infants.