We formulate Non-Relativistic Quantum Chromodynamics (NRQCD) on a lattice which is boosted relative to the usual discretization frame. Moving NRQCD (mNRQCD) allows us to treat the momentum for the heavy quark arising from the frame choice exactly. We derive mNRQCD through O(1/m^2,v^4), as accurate as the NRQCD action in present use, both in the continuum and on the lattice with O(a^4) improvements. We have carried out extensive tests of the formalism through calculations of two-point correlators for both heavy-heavy (bottomonium) and heavy-light (B_s) mesons in 2+1 flavor lattice QCD and obtained nonperturbative determinations of energy shift and external momentum renormalization. Comparison to perturbation theory at O(alpha_s) is also made. The results demonstrate the effectiveness of mNRQCD. In particular we show that the decay constants of heavy-light and heavy-heavy mesons can be calculated with small systematic errors up to much larger momenta than with standard NRQCD.