We present the full details of a calculation at next-to-leading order of the momentum diffusion coefficient of a heavy quark in a hot, weakly coupled, QCD plasma. Corrections arise at O(g_s); physically they represent interference between overlapping scatterings, as well as soft, electric scale (p ∼ gT) gauge field physics, which we treat using the hard thermal loop (HTL) effective theory. In 3-color, 3-flavor QCD, the momentum diffusion constant of a fundamental representation heavy quark at NLO is κ = (16π/3)α_s²T³(ln (1/g_s)+0.07428+1.9026g_s). We extend the computation to a heavy fundamental representation ``probe'' quark in large N_c, N = 4 Super Yang-Mills theory, where the result is κ^(SYM) = (λ²T³/6π)(ln (1/√λ)+0.4304+0.8010√λ) (where λ = g²N_c is the t'Hooft coupling). In the absence of some resummation technique, the convergence of perturbation theory is poor.