We calculate the Next-to-Leading Order (NLO) QCD corrections to Z b anti-b production in hadronic collisions including full bottom-quark mass effects. We present results for the total cross section and the invariant mass distribution of the bottom-quark jet pair at the Fermilab Tevatron p anti-p collider. We perform a detailed comparison with a calculation that considers massless bottom quarks, as implemented in the Monte Carlo program MCFM. We find that neglecting bottom-quark mass effects overestimates the total NLO QCD cross section for Z b anti-b production at the Tevatron by about 7%, independent of the choice of the renormalization and factorization scales. Moreover, bottom-quark mass effects can impact the shape of the bottom-quark pair invariant mass distribution, in particular in the low invariant mass region.