Selain kepala negara, Malaysia juga dipimpin oleh seorang kepala pemerintahan, yaitu Perdana Menteri yang dipilih oleh Yang di-Pertuan Agong atau Raja Malaysia di antara anggota parlemen yang mendapat dukungan mayoritas di majelis rendah. Biasanya pemimpin partai politik terkuat dalam parlemen Dewan Rakyat yang dipilih menjadi perdana menteri. Sejak kemerdekaannya pada tahun 1957 hingga 2018, Perdana Menteri semuanya berasal dari United Malays National Organisation (bahasa Indonesia: Organisasi Kebangsaan Melayu Bersatu; UMNO), partai politik terbesar dalam koalisi Barisan Nasional (dikenal sebagai Parti Perikatan hingga 1973). Teori "Rahman" disebut-sebut mewakili huruf depan dari keenam mantan perdana menteri dari Rahman hingga Najib. Setelah itu, dua perdana menteri berasal dari Partai Pribumi Bersatu Malaysia dengan dua aliansi yang berbeda di mana Mahathir Mohamad oleh Pakatan Harapan dan Mahiaddin Md. Yasin (atau Muhyiddin Yassin) oleh Perikatan Nasional.
Ada kekhawatiran bahwa UMNO maupun Partai Islam Se-Malaysia (PAS) akan melarang seorang non-Bumiputera (misalnya dari etnis Tionghoa) menjadi Perdana Menteri, tetapi pemerintah telah berulang kali meyakinkan para rakyat bahwa konsitiusi Malaysia tidak mengharuskan Perdana Menteri harus seorang Bumiputera.