We propose a new non-perturbative approach to hadronic interactions at high energies and small momentum transfer, which is based on the scale anomaly of QCD and emphasizes the role of semi-classical vacuum fields. We find that the hadron scattering amplitudes exhibit Regge behavior and evaluate the intercept alpha(0) of the corresponding trajectory. Both the intercept and the scale for the slope of the trajectory appear to be determined by the energy density of non-perturbative QCD vacuum (the gluon condensate). Numerically, we find Delta = alpha(0) - 1 = 0.08 -0.1, consistent with the values ascribed phenomenologically to the ``soft'' Pomeron. For arbitrary numbers of colors N_c and flavors N_f, Delta is found to be proportional to (N_f/N_c)^2; however, in the large N_c (N_f fixed) limit, Delta \sim N_c^0.