Lebanon has been a reluctant host to Palestinian refugees since 1948. A mainstay of Lebanese policies vis-à-vis the Palestinian refugees has been preventing their permanent integration and settlement in the country. The question of naturalizing refugees is one of the most contentious political issues in Lebanon today. Palestinian refugees tend to live in conflict-ridden environments, often at the margins of the host society. This first of all applies to the camp-based refugees, who languish in dilapidated and overcrowded camps. Unable to return to Palestine and marginalized by the host society, they are caught in a legal limbo. In order to understand the complex legal regime that governs their refugee status, it is necessary to examine their rights as refugees in international law, regionally as hosted by Arab League states and nationally as residents of Lebanon. The rights regime is complex and contributes to a critical ‘protection gap' for the refugees. This article demonstrates how this protection gap was created and widened by historically contingent, international, regional and national legal rights regimes.