This study was conducted to gauge the nature and level of organizational legitimacy of private higher education institutions (PHEIs) in Ethiopia through the perspectives of regulators involved in accrediting and auditing private institutions. The study adopted a mixed-methods approach, particularly the explanatory sequential design, and used questionnaire, documentary evidence, and interview as principal means of data collection. One hundred and twenty-one regulators were involved in the survey and ten regulators participated in the in-depth interview. The findings revealed that both the overall rating of PHEIs and the various categories of legitimacy identified as procedural, consequential, structural, personal, and linkage received average ratings by regulators. This denotes a threshold level of acceptance suggesting the need for a more substantial legitimacy level that the Ethiopian private higher education sector should attain if it seeks to earn heightened credibility and active support from stakeholders. Conclusions and implications of the study at the nexus of theory, policy, and practice are discussed.