The internal audit function is an essential part of an organization, which if functioning effectively should ensure transparency, accountability, and efficient service delivery. In recent times, the public health sector has become the focus of debate among stakeholders who decry the poor state of health facilities, poor service delivery, misappropriation of funds, misuse/mismanagement of assets, fraud. This has resulted in an increase in private hospital patronage as patients prefer private hospitals to public hospitals. The major objective of this study is to assess those attributes that influence internal audit effectiveness in the Nigerian public health sector. The study employed exploratory and case study research design in examining and understanding the problem. Data for this study was collected using semi structured face-face interviews with the head of department and unit heads of the internal audit department of the sample institutions and review of relevant documents (audit manuals and reports) where available. The results reveal that internal quality (scope of work, independence, communication skill, staffing and staff expertise) and management support (funding, response to audit finding and staff training) are key factors affecting internal audit effectiveness, while audit attributes and organizational setting are relevant but not key factors in determining internal audit effectiveness. It is therefore recommended that the scope of internal audit work should be broadened to include risk assessment, compliance audit and internal control review to enhance audit quality. Similarly, audit reports should be prepared and communicated more regularly and adequate follow up should be made to ensure their implementation. Management should provide adequate support in terms of employing permanent and qualified staff for the audit department and also provide regular technical training to ensure that the auditors are up to date in terms of skills and expertise to carry out their assignments effectively.