Prelacteal feeding practices are associated with an increased risk of diarrhoea and many early-life diseases. This paper examined trends and predictors of prelacteal feeding practices in Nigeria. A sample of 6416 infants aged 0–6 months from the Nigeria Demographic and Health Survey data for the period (2003–2013) was used. Trends and multilevel logistic regression analyses were used to determine the predictors. The trends of prelacteal feeding rates fluctuated between 55% and 66% over the study period and were significantly lower among mothers with secondary or higher levels of education (13.1%, 95% confidence interval (CI): 0.54–25.9, p-value = 0.041), delivered at the health facility (13.7%, CI: 1.39–25.9, p-value = 0.029), from more affluent households (18.7%, CI: 1.53–35.9, p-value = 0.033), and lived in urban areas (26.9%, CI: 18.3–35.5, p-value < 0.001). Multivariable analyses revealed that mothers with no schooling, younger mothers (aged 15–24 years), mothers who delivered at home, and delivered by caesarean section were more likely to introduce prelacteal feeds. Many mothers still engage in prelacteal feeding practices in Nigeria, with prelacteal feeding more prevalent in young mothers, mothers with no schooling, and mothers who delivered at home. Interventions involving community health volunteers are needed to improve feeding practices in Nigeria.