We determine to order alpha^3 the so-called residual mass in the lattice regularisation of the Heavy Quark Effective Theory for Nf=2. Our (gauge-invariant) strategy makes use of Numerical Stochastic Perturbation Theory to compute the static interquark potential where the above mentioned mass term appears as an additive contribution. We discuss how the new coefficient we compute in the expansion of the residual mass can improve the determination of the (MS bar) mass of the b-quark from lattice simulations of the Heavy Quark Effective Theory.