We derive the perturbative four-dimensional effective theory describing heterotic M-theory with branes and anti-branes in the bulk space. The back-reaction of both the branes and anti-branes is explicitly included. To first order in the heterotic strong-coupling expansion, we find that the forces on branes and anti-branes vanish and that the KKLT procedure of simply adding to the supersymmetric theory the probe approximation to the energy density of the anti-brane reproduces the correct potential. However, there are additional non-supersymmetric corrections to the gauge-kinetic functions and matter terms. The new correction to the gauge kinetic functions is important in a discussion of moduli stabilization. At second order in the strong-coupling expansion, we find that the forces on the branes and anti-branes become non-vanishing. These forces are not precisely in the naive form that one may have anticipated and, being second order in the small parameter of the strong-coupling expansion, they are relatively weak. This suggests that moduli stabilization in heterotic models with anti-branes is achievable.