A theoretical approach is presented that accounts for the influence of high pressure background gases on the vapor-to-liquid nucleation process. The key idea is to treat the carrier gas pressure as a perturbation parameter that modifies the properties of the nucleating substance. Two important mechanisms are identified in this respect: With increasing carrier gas pressure, the saturated vapor density tends to increase (enhancement effect), whereas the surface tension generally decreases. Several routes to obtain data for these pressure effects are outlined, in particular for the vapor-gas mixtures that have been studied experimentally. (The results of these expansion wave tube experiments are presented in Paper II of this paper [J. Chem. Phys. 111, 8535 (1999), following paper.]) Using classical nucleation theory, a criterion is then derived for the "pressure perturbation'' approach to be valid: x(g)(eq) much less than(S-1)/S, where x(g)(eq) is the carrier gas solubility in the liquid phase, and S is the supersaturation ratio. For the semiphenomenological Kalikmanov-Van Dongen model, the implications of the enhancement effect and surface tension decrease are briefly discussed. We also illustrate how these two effects can be obtained from (binary) density functional theory. Results of the latter for a mixture of Lennard-Jones particles are presented, with potential parameters that are characteristic for n-hexane with several carrier gases.