We perform the non-perturbative (quenched) renormalization of the
chromo-magnetic operator in Heavy Quark Effective Theory and its three-loop
matching to QCD. At order 1/m of the expansion, the operator is responsible
for the mass splitting between the pseudoscalar and vector B-mesons. These new
computed factors are affected by an uncertainty negligible in comparison to
the known bare matrix element of the operator between B-states. Furthermore,
they push the quenched determination of the spin splitting for the Bs-meson
much closer to its experimental value than the previous perturbatively
renormalized computations. The renormalization factor for three commonly used
heavy quark actions and the Wilson gauge action and useful parametrizations of
the matching coefficient are provided.