We develop a statistical method for using multicolor photometry to determine distances using Cepheid variables including the effects of temperature, extinction, and metallicity and apply it to UBVRIJHK photometry of 694 Cepheids in 17 galaxies. We derive homogeneous distance, extinction and uncertainty estimates for four models, starting from the standard extragalactic method and then adding the physical effects of temperature distributions, extinction distributions, requiring positive definite extinctions, and metallicity. While we find general agreement with published distances when we make similar systematic assumptions, there is a clear problem in the standard distances because they require Cepheids with negative extinctions, particularly in low metallicity galaxies, unless the mean LMC extinction exceeds E(B-V) > 0.25. The problem can be explained by the physically expected metallicity dependence of the Cepheid distance scale, where metal-poor Cepheids are hotter and fainter than metal-rich Cepheids. For V and I we found that the mean magnitude change is -0.14 +/- 0.14 mag/dex and the mean color change is 0.13 +/- 0.04 mag/dex, with the change in color dominating the change in distance. The effect on Type Ia supernova estimates of the Hubble constant is dramatic because most were found in the metal poor galaxies with the bluest Cepheids. The Type Ia Multi-color Light Curve Shape (MLCS) method estimate for H_0 formally rises from 69 +/- 8 km/s Mpc to 80 +/- 6 km/s Mpc with the metallicity correction.

54 pages, 7 figures, 4 tables, submitted to ApJ