Globalization and ever changing business environment requires modern business entities as well as State-Owned Enterprises (SOEs) to be more flexible and sensitive on various stakeholders’ needs by effectively utilizing their core competencies and resources. This development requires SOEs to be innovative and entrepreneurial in identifying and acquiring new business opportunities. However, previous studies revealed the existence of certain structural and organizational factors, which restrain Entrepreneurship Orientation (EO) among SOEs. Even though past findings are significant, most of the studies focused on developed nations. Against the backdrop of developing countries, especially in the Southest-East Asia region, this study attempts to investigate the management challenges in order to inculcate EO among Malaysian SOEs. The semi-structured interviews with top managers at five SOEs’ holding companies in Peninsular Malaysia were being used. This paper found the major challenges confronting the top management were related to organizational culture,
quality of human resources and governance system.