For a long time, the effect of a crowded cellular environment on protein dynamics has been largely ignored. Recent experiments indicate that proteins diffuse more slowly in a living cell than in a diluted solution, and further studies suggest that the diffusion depends on the local surroundings. Here, detailed insight into how diffusion depends on protein-protein contacts is presented based on extensive all-atom molecular dynamics simulations of concentrated villin headpiece solutions. After force field adjustments in the form of increased protein water interactions to reproduce experimental data, translational and rotational diffusion was analyzed in detail. Although internal protein dynamics remained largely unaltered, rotational diffusion was found to slow down more significantly than translational diffusion as the protein concentration increased. The decrease in diffusion is interpreted in terms of a transient formation of protein clusters. These clusters persist on sub-microsecond time scales and follow distributions that increasingly shift toward larger cluster size with increasing protein concentrations. Weighting diffusion coefficients estimated for different clusters extracted from the simulations with the distribution of clusters largely reproduces the overall observed diffusion rates, suggesting that transient cluster formation is a primary cause for a slow-down in diffusion upon crowding with other proteins.