This paper examines ways that Algerians responded to restrictive policies regulating pilgrimage to Mecca and the Holy Places (hajj) during the colonial era. Following a period of improvisation from roughly 1830-60, French authorities came to see the hajj as a potential vehicle to advance colonial power. Beginning in the second half of the nineteenth century, they developed an elaborate system of regulations to control the hajj in the interests of political control and public health, and, more broadly, they tried to use the hajj to cultivate proper colonial subjects. At the centerpiece of these efforts was the travel permit or a special passport issued to Algerian candidates to the hajj. The process of issuing travel documents was complicated, expensive, and favored those who had a good understanding of the colonial system, its networks of patronage, unspoken rules, etc. This limited the hajj a select group. Such regulations combined with outright bans on hajj travel enforced in the last decades of the nineteenth century to make the hajj inaccessible to the vast majority of Algerians. They reacted in a variety of ways, one of which was to debark on pilgrimage without proper papers, making a “clandestine hajj,” an offense punishable by fines and imprisonment. Drawing on research in colonial documents held in France and Algeria, this paper will shed light on this activity. The colonial archive consists of documents from the Governor General’s office and local administrators in Algeria as well as correspondence from consulates across North Africa to Jeddah. This material speaks well to the size and social composition of this group, as well as its strategies for success.