We describe a strategy for a non-perturbative computation of the b-quark mass to leading order in 1/m in the Heavy Quark Effective Theory (HQET). The approach avoids the perturbative subtraction of power law divergencies, and the continuum limit may be taken. First numerical results in the quenched approximation demonstrate the potential of the method with a preliminary result (m) over bar ((MS) over bar)(b) (4GeV) = 4.56(2)(7) GeV. In principle, the idea may also be applied to the matching of composite operators or the computation of 1/m corrections in HQET.