This chapter examines the state/horse power complex that defined political power in the Southern Red Sea Region (SRSR) prior to the military modernisations of the twentieth century. The SRSR is a sub-region of the Indian Ocean World that encompasses parts of modern-day Sudan, Eritrea, Ethiopia, Djibouti, Somalia, Yemen, and Saudi Arabia. Historically, state power in the SRSR was established, consolidated, maintained, and expanded through violence and the deployment of war horses was central to these processes. The state/horse power complex was only disrupted by the introduction of large quantities of mass-produced European arms. As infantries became the core of the armed forces in the region, cavalries were dismantled and horses were relegated to symbolic roles in newly invented cultural traditions.