The contribution of private higher education institutions (PHEIs) in Malaysia is important to the higher education industry. Among the roles of PHEIs are providing a pathway to local and international students to the tertiary level of education, contributing towards making Malaysia an international and highly reputable hub for higher education as well as limiting the flow of our intellects to foreign countries. However, there has been a major concern over the performance of PHEIs. Due to the volatility of the higher education landscape, many local PHEIs are facing with serious issues and challenges which affect their organizational self-sustainability. If the issues and challenges are not seriously addressed, it could impede the growth of PHEIs as well as become the barriers to PHEIs to serve their roles in Malaysia higher education sector. This conceptual paper provides some insights into the issues and challenges of PHEIs in Malaysia. It also identified leadership and innovation as the critical success factors for PHEIs organizational self-sustainability and proposed that these two independent variables are tested in future research.