We report the non-perturbative tuning of parameters--- kappa_c, kappa_b, and kappa_crit ---that determine the heavy-quark mass in the Fermilab action. This requires the computation of the masses of Ds^(*) and Bs^(*) mesons comprised of a Fermilab heavy quark and a staggered light quark. Additionally, we report the hyperfine splittings for Ds and Bs mesons as a cross-check of our simulation and analysis methods. We find a splitting of 145 +/- 15 MeV for the Ds system and 40 +/- 9 MeV for the Bs system. These are in good agreement with the Particle Data Group average values of 143.9 +/- 0.4 MeV and 46.1 +/- 1.5 MeV, respectively. The calculations are carried out with the MILC 2+1 flavor gauge configurations at three lattice spacings $a$ approximately 0.15, 0.12, and 0.09 fm.