Attendance at high-quality early childhood education and care services can have positive impacts on children’s learning and development, particularly for disadvantaged children. Aboriginal children in the Northern Territory are among the most disadvantaged in Australia and stand to benefit in the short- and long-term from attending high-quality and culturally safe early childhood education and care. Few studies, however, have evaluated how early childhood education and care services can support Aboriginal children’s learning and development, or reported on the challenges of conducting such evaluations. This article reports on an evaluation of the Arrwekele Akaltye-Irretyeke Apmere Centre for Aboriginal children in Alice Springs, Australia, which employed a culturally-adapted Abecedarian approach. The evaluation drew from interviews, classroom observations, document review, and language and developmental assessments to report findings about quality, cultural safety, acceptability to the community and children’s language and development. The findings show that despite the Centre facing challenges during its establishment, by the end of the evaluation children were attending the Centre and receiving high-quality service. The service was overwhelmingly valued by interviewees from families and the community and there were indications of positive outcomes in children’s language and development. Insights for the design of similar evaluations are discussed, such as the need for more rigorous and consistent data collection techniques, a larger sample, and the inclusion of a wider range of perspectives.