The strategic location, economic and political stabilities, regional and international developments and a relatively cheaper cost of living collectively contribute to the development and growth of education in Malaysia, in line with the vision of becoming a regional hub of education excellence. To attract more foreign students, Private Higher Education Institutions (PHEIs) were encouraged to provide world-class qualifications and holistic education through collaborations with foreign academic partners. However, the education industry was ill equipped to meet the issues that emerged with the influx of foreign students and the underlying advantages were not sufficient to ensure sustainable and continuous recruitment of foreign students. Raising the standards of the infrastructure alone is not enough; there is a need to look at the existing Policies, which form the backbone of a successful education export industry. This Study investigates the impact of Education and Immigration Policies on the recruitment of foreign students to PHEIs in Malaysia using the Cheng and Cheung Policy Analysis Framework and the qualitative and quantitative research paradigms. It concludes that the Policy Analysis Framework is suitable in the current context and that generally the findings suggest that Education and Immigration Policies impact the recruitment of foreign students to PHEIs in Malaysia. Specifically, Education Policies, in relation to the administration of the Institutions, such as marketing strategies, and the teaching of the Compulsory Subjects, affect recruitment of foreign students. As for Immigration Policies, the carrying of Student Passports is inconvenient and the alternative of the International Student Card is timely and necessary and the Immigration Procedures should be more student-friendly. The policy to allow foreign students to work may not increase the number of foreign students, as the current conditions are too restrictive. To overcome the current shortcomings in the policies concerned, there is a need for the review of these policies by looking at their formulation, implementation and impact. Any attempts to re-draw the policies must be supported with substantive research and participation from PHEIs. Policies are only successful if the objectives are formulated and implemented correctly and stakeholders’ participation is incorporated from the very beginning.