We calculate the Next-to-Leading Order (NLO) QCD corrections to W-b-bbar production including full bottom-quark mass effects. We study the impact of NLO QCD corrections on the total cross section and invariant mass distribution of the bottom-quark jet pair at the Fermilab Tevatron p-pbar collider. We perform a detailed comparison with a calculation that considers massless bottom quarks. We find that neglecting bottom-quark mass effects overestimates the NLO total cross-section for W-b-bbar production at the Tevatron by about 8% independent of the choice of renormalization and factorization scale.