Postnatal care (PNC) is critical for the survival of newborns. In Zambia, despite emphasis on PNC by the government and international organizations, PNC coverage continues to be low. This study assessed the demographic and socioeconomic factors associated with newborns’ receipt of PNC and the timing of first PNC in Zambia. Based on data from the 2013-14 Zambia Demographic and Health Survey (ZDHS), this study used bivariate, binary, and multinomial logistic regression analyses to examine PNC for births at home and at health facilities. The results indicate different factors associated with PNC and timing at which newborns receive their first PNC between births delivered at home and at health facilities. For home births, perceived child size at birth by mothers, region of residence, access or exposure to media, and mothers’ numbers of ANC visits are the major determinants of PNC. Regarding timing of first PNC within 2 days of childbirth, among newborns delivered at home the major determinants are perceived child size at birth by mothers, region of residence, mothers’ access to media, and number of ANC visits. In contrast, among newborns delivered in a facility, perceived size at birth, region of residence, and mothers’ employment status are the only factors associated with receiving PNC within the first 2 days. Therefore, recommendation is made to encourage delivery in a health facility, to emphasize the importance of ANC visits, and to disseminate information through various media and innovative programs such as Information Education and Communication (IEC).