Recent work on crime fiction has highlighted the genre’s increasingly transnational focus and the growing number of migrant detectives. Matsotsi, a little-known Nyanja text published in Zambia in the early 1960s, provides a much earlier example of this figure in Sergeant Balala, an Angolan detective fighting to contain the tsotsi menace in Johannesburg, South Africa. Matsotsi, however, does more than point to cross-border detection as a means of elucidating transnational relationships. Shonga and Zulu’s text manipulates the genres of the detective novel and the bildungsroman to tell a story about the relationships among the individual, the state, and the wider region at a key moment in southern African history, when Zambia and Malawi were on the cusp of independence. Although African language writing has often been considered too localized to be used for nationalist purposes, here it is mobilized for the purpose of state-making in a transnational context.