Human-mediated biological exchange has had global social and ecological impacts. In sub-Saharan Africa, several domestic and commensal animals were introduced from Asia in the pre-modern period; however, the timing and nature of these introductions remain contentious. One model supports introduction to the eastern African coast after the mid-first millennium CE, while another posits introduction dating back to 3000 BCE. These distinct scenarios have implications for understanding the emergence of long-distance maritime connectivity, and the ecological and economic impacts of introduced species. Resolution of this longstanding debate requires new efforts, given the lack of well-dated fauna from high-precision excavations, and ambiguous osteomorphological identifications. We analysed faunal remains from 22 eastern African sites spanning a wide geographic and chronological range, and applied biomolecular techniques to confirm identifications of two Asian taxa: domestic chicken (Gallus gallus) and black rat (Rattus rattus). Our approach included ancient DNA (aDNA) analysis aided by BLAST-based bioinformatics, Zooarchaeology by Mass Spectrometry (ZooMS) collagen fingerprinting, and direct AMS (accelerator mass spectrometry) radiocarbon dating. Our results support a late, mid-first millennium CE introduction of these species. We discuss the implications of our findings for models of biological exchange, and emphasize the applicability of our approach to tropical areas with poor bone preservation.