Homogeneous power counting in Non-Relativistic QCD with the velocity renormalization group (vNRQCD) necessitates the existence of both soft and ultrasoft gluons. We show that vNRQCD operators involving soft fields can be put in a manifestly gauge invariant form by exploiting gauge invariant gluon building blocks. These building blocks contain Wilson lines and are analogous to those used in SCET. This greatly reduces the size of the operator basis, and hence simplifies calculations at subleading order, including the number of diagrams, and structure of operator running. In this formulation the ghost fields only appear in the soft kinetic Lagrangian and not in interactions with other fields. Also, the contributions from the Coulomb region which can cause pinch singularities are automatically avoided in soft loops.