Detailed simulations were performed on beam loss rates in the vicinity of the Tevatron Collider detectors due to beam-gas nuclear elastic interactions. It turns out that this component, not intercepted by the Tevatron collimation system, can drive the accelerator-related background rates in the CDF and D0 detectors, exceeding those due to outscattering from collimator jaws, inelastic beam-gas interactions and other processes. Results of realistic simulations with the STRUCT and MARS codes are presented for the interaction region components, forward proton detectors and the CDF and D0 subdetectors. Beam loss induced background rates calculated in the CDF West beam halo monitors are in a good agreement with recent measurements. It is shown that a steel mask in the Roman Pot station region can reduce the background rates at the collider detectors by almost an order of magnitude.