Tourism in Africa was entangled with colonialism from the start. However, after the Second World War it became an integral part of the colonising powers’ development agenda, albeit one that has received little scholarly attention so far. This presented African states with a serious dilemma when most of them gained independence during the 1960s. On the one hand, tourism promised to stimulate economic growth, provide much needed foreign currency, and create employment opportunities. On the other hand, international tourism had the potential to threaten the economic independence of post-colonial states and perpetuate colonial stereotypes, as well as international and local power imbalances and inequalities. The newly elected governments had to deal with this “colonial baggage.” This article focusses on the transition from colonial to post-colonial tourism in two East African countries, Kenya and Tanzania. I explore how the late colonial government pursued tourism as a development strategy for the region. I also demonstrate how Kenya and Tanzania approached tourism and its colonial legacies in different ways after independence. To trace their respective tourism histories, I draw on published reports and newspaper articles, historical research literature, in particular, from tourism scholars of various disciplines, as well as archival sources.