Bottlenose dolphin (Tursiops sp.) populations often show small-scale genetic differentiation and have a capacity to adapt both their social strategies and structure to local environmental conditions. Here we investigate population structure and genetic diversity of Indo-Pacific bottlenose dolphins (Tursiops aduncus) in the western Indian Ocean, with special reference to Zanzibar, Tanzania. The Indo-Pacific bottlenose dolphins off Zanzibar were previously hunted and are subject to high levels of bycatch and negative impact from tourism. A recent study has indicated a limited exchange of reproducing females between northern and southern Zanzibar. Mitochondrial DNA sequence (mtDNA 429bp) variation and autosomal genotypes (7 microsatellite loci) was used to assess genetic variation and differentiation among tissue samples from Zanzibar (n=91) Mayotte (n=12) and Oman (n=4). The results showed a much higher amount of differentiation for mtDNA than autosomal DNA between northern and southern Zanzibar suggesting female philopatry with greater dispersal by males than females. Genetic diversity levels were relatively high in all areas and there were no indications of any recent reduction in effective population size, except in Mayotte where indications of a recent bottleneck encourage further analyses. Further, the close relationship and lack of clear structuring, with several shared haplotypes among regions, suggest a relatively recent common founder population for the Indo-Pacific bottlenose dolphins in the western Indian Ocean. Based on the high differentiation in mtDNA between northern and southern Zanzibar and that local growth rates in large part will be determined by female breeding success, we suggest that the Indo-Pacific bottlenose dolphins off northern and southern Zanzibar should be treated as separate management units.