We calculate the self-energy of the heavy quark to O in nonrelativistic QCD (NRQCD) on the lattice. We use the lowest-order (in 1M) NRQCD action which includes the time derivative and kinetic energy terms, but we ignore spin effects. Results are given for the wave-function renormalization, mass renormalization, and energy shift. Our results agree with the lowest-order static effective field theory as Ma, where Ma is the quark mass in lattice units. At values of Ma appropriate to b- and c-quark calculations, the differences are significant. We also consider 1Ma corrections to the static theory arising from the kinetic term.