What explains states’ sub-national territorial reach? While large parts of the state-building literature have focused on national capabilities, little is yet known about the determinants of the unevenness of state presence on the subnational level. To fill this gap, we look at early attempts at state-building: we investigate the processes of state penetration in the former colony of German East Africa. Contrary to previous studies – which largely emphasized antecedent or structural factors – we argue that geographical patterns of state penetration have been driven by the state’s strategic imperative to solidify control over territory and establish political stability. We test our propositions using an original, geo-referenced grid-cell dataset for the years 1890 to 1909 based on extensive historical records in German colonial yearbooks and maps.