We demonstrate a first-principles method to compute all factors entering the vacancy-mediated self-diffusion coefficient. Using density functional theory calculations of fcc Al as an illustrative case, we determine the energetic and entropic contributions to vacancy formation and atomic migration. These results yield a quantitative description of the migration energy and vibrational prefactor via transition state theory. The calculated diffusion parameters and coefficients show remarkably good agreement with experiments. We provide a simple physical picture for the positive entropic contributions.