Ever since 9/11, dhows, or Indian Ocean sailing vessels, have been viewed as inherently threatening to national and international security, as government authorities suspect that they are used to smuggle weapons and militants. Most recently, dhows that transport charcoal from Somalia to the United Arab Emirates have been implicated in funding al-Shabaab, a militant group. Rather than taking a presentist view, this article argues that these security concerns have emerged from a deep-rooted anxiety over mobility in the Indian Ocean, as dhow networks challenge state sovereignty. Dhows, once habituated to a world of layered sovereignty, have now been forced to contend with the boundaries of centralized sovereign states. Moreover, government and international law and policy such as economic liberalization in India have made the dhow trade more precarious, and pushed it into a shadow economy that ultimately converges with financing for al-Shabaab, even as this economy sustains seafaring populations in the midst of economic precarity. Tracing dhow itineraries in tandem with shifting regulations across South Asia and East Africa, the article charts an alternate course of Indian Ocean history, one in which dhow networks navigate multiple regulatory regimes and global shifts by operating in a shadow economy at the margins of states.