The internationalisation of higher education has become a strategic priority for governments seeking to strengthen global competitiveness, attract talent and expand education exports. In Malaysia, successive national policies have positioned private higher education institutions (HEIs) as key contributors to international student recruitment. However, little is known about how private HEIs perceive and respond to these policies despite their central role in achieving national internationalisation goals. This study examined private HEIs' perceptions of national policy support, the institutional strategies adopted in response and the implementation challenges encountered. Guided by institutional theory, a mixed-method survey of 113 Malaysian private HEIs combined quantitative and qualitative analyses to examine policy implementation. The findings revealed a persistent implementation gap. Although national policies were generally perceived as supportive in intent, their effectiveness was constrained by fragmented inter-agency coordination, limited resource support and policy complexity. Larger private HEIs were better able to implement substantive, largely self-funded strategies, whereas smaller institutions relied on low-cost measures and informal workarounds, reflecting unequal institutional capacity and symbolic compliance. The study demonstrates how institutional theory explains the interaction between market dependence and institutional capacity in shaping organisational responses to national internationalisation policies. It highlights the need for differentiated capacity-sensitive policy support to strengthen implementation and advance Malaysia's internationalisation agenda more equitably.