The breakdown of the Stokes-Einstein relation (SER) in three model metallic liquids is investigated via molecular dynamics simulations. It is found that the breakdown of SER is closely correlated with the clustering behavior of well-packed atoms. When the SER breaks down, many cluster properties have almost the same value in these metallic liquids. At the breakdown temperature of SER, the temperature dependence of the number of clusters begins to deviate from a linear increase and the average number of well-packed atoms in the clusters reaches about 2, which indicates an increase in structure heterogeneity. Moreover, the size of the largest cluster shows a direct correlation with the SER. Therefore, our study provides a possible structural origin for the breakdown of SER in metallic liquids.