We present a new approach to moduli stabilization in Calabi-Yau compactifications of Heterotic M-theory. Our approach is based in a detailed mathematical understanding of the moduli dependence of supersymmetric heterotic vacua. We will discuss a scenario to stabilize all geometric moduli - that is, the complex structure, Kahler moduli and the dilaton - without Neveu-Schwarz three-form flux. This is accomplished using the gauge bundle required in any heterotic compactification, whose perturbative effects on the moduli are combined with non-perturbative corrections. We argue that, for appropriate gauge bundles, all complex structure and a large number of other moduli can be perturbatively stabilized. At this stage, the remaining moduli space consists of Minkowski vacua. Finally, we incorporate non-perturbative effects such as gaugino condensation and/or instantons which are strongly constrained by the anomalous U(1) symmetries arising from the required bundle constructions.