In recent years, the Kenyan government has increasingly developed labor export policies to secure employment for its nationals in the Gulf countries. Between 100,000 – 300,000 Kenyan migrants—mostly unskilled laborers — are represented in the Gulf countries’ population, and this number is expected to grow given the high demand for inexpensive foreign workers in the Gulf countries. Kenya’s labor export policies facilitate important economic strategies that enable the government to address the Gulf countries’ labor shortages, while easing the growing unemployment problems in Ken-ya. However, the Kenyan government has not formed a comprehensive protection policy nor developed bilateral labor arrangements and institutional/diplomatic capacity to safeguard Kenyans from labor violations and exploitation. This paper examines the Kenyan government's complex role in and its challenges with protecting its nationals in the Gulf countries, while analyzing the emerging contemporary migration flow between Kenya and the Gulf countries, mainly in Saudi Arabia and the United Arab Emirates. We argue that the power asymmetry between the Kenyan and Gulf governments directly affects bilateral migration policymaking, particularly labor protection and migrant welfare. This paper further asserts that macro-factors - the Gulf countries’ bilateral trade with Kenya, humanitarian aid assistance as “soft-power”, and open immigration systems - have constrained the Kenyan government's ability to protect its nationals in the host countries.