Early childhood is a critical period of rapid physical, cognitive, and psycho-social development of a child. The quality of care and education which a child receives at this crucial age will determine to a great extent the level of his/her physical and cognitive development in the future. In Nigeria, Early Childhood Care, Development and Education (ECCDE) is an aspect of Universal Basic Education which was introduced in 1999 to increase the access of children to basic education and improve the state of education in the country. While all hands are on deck to ensure successful implementation and achievement of the objectives of the scheme, it is unfortunate that ECCDE is facing some challenges thus making it unrecognized in Nigeria. This paper examines the challenges of early childhood education in Nigeria. To improve the situation, the following measures are recommended: establishment of more public creche, kindergarten, and nursery schools by the government; enforcement of the use of mother tongue in the teaching of children; training more personnel in the field of early childhood education in tertiary institutions; and introducing unified curriculum as well as providing more infrastructures.