RAPD markers were used to estimate levels of genetic diversity and structure among twelve East African Tall (EAT) coconut (Cocos nucifera L.) accessions that are maintained at Chambezi station. Ten primers were used in the analysis of 120 accessions. Cluster analysis was performed based on Jaccard’s coefficient and Nei genetic distances. Further analyses included principal coordinate analysis (PCA) and finally bootstrap analysis. The cluster analysis revealed two main clusters. One cluster contained provenances from Lindi and Mtwara regions (south) and those from Coast and Dar es Salaam regions (central); the second had provenances from Tanga region, which is the northern part of the coastal belt. A similar distribution of provenances was shown by the results of the principal coordinate analysis, whose first three coordinates explained 56% of the total variation. The results were able to discriminate between the different provenances and provide evidence of the different origins for the coconut palms in the northern and southern parts of coastal coconut-growing belt. The two major clusters concur well with the history and distribution of coconuts in the coastal belt of Tanzania.