Urban challenges are increasingly framed in the context of broader objectives of socio-economic development and macro-regional evolutions. Cities and the myriad networks in which they are embedded have thus been placed at the center of regional integration agendas. This paper benchmarks contemporary regional integration levels in the Horn of Africa by examining its cities’ connectivities in transport networks. To this end, we specify a composite network consisting of air/train/road connectivity and analyze cities’ eigenvector and betweenness centralities within these networks. We find that the importance of national spaces for inter-city connectivity is much more evident in the Horn of Africa than in other parts of the world, which is also visible in the peripheralization of cities in borderlands. We argue that the region’s connectivity needs to be understood from a multiscalar and multimodal perspective and provide a baseline against which the impact of future interventions aimed at enhancing city connectivity/regional integration can be examined.