The ALESS survey has followed up on a sample of 122 sub-millimeter sources in the Extended Chandra Deep Field South at 870 mu m with the Atacama Large Millimeter Array (ALMA), allowing us to pinpoint the positions of sub-millimeter galaxies (SMGs) to similar to 0.3 arcsec and to find their precise counterparts at different wavelengths. This enabled the first compilation of the multi-wavelength spectral energy distributions (SEDs) of a statistically reliable survey of SMGs. In this paper, we present a new calibration of the MAGPHYS SED modeling code that is optimized to fit these ultraviolet-to-radio SEDs of z > 1 star-forming galaxies using an energy balance technique to connect the emission from stellar populations, dust attenuation, and dust emission in a physically consistent way. We derive statistically and physically robust estimates of the photometric redshifts and physical parameters (such as stellar masses, dust attenuation, star formation rates (SFRs), and dust masses) for the ALESS SMGs. We find that the ALESS SMGs have median stellar mass M-* = 8.9 +/- 0.1 x 10(10) M-circle dot, median SFR = 280 +/- 70 M-circle dot yr(-1), median overall V-band dust attenuation A(V) = 1.9 +/- 0.2 mag, median dust mass M-dust = (5.6 +/- 1.0) x 10(8) M-circle dot, and median average dust temperature T-dust similar or equal to 40 K. We find that the average intrinsic SED of the ALESS SMGs resembles that of local ultra-luminous infrared galaxies in the infrared range, but the stellar emission of our average SMG is brighter and bluer, indicating lower dust attenuation, possibly because they are more extended. We explore how the average SEDs vary with different parameters (redshift, sub-millimeter flux, dust attenuation, and total infrared luminosity), and we provide a new set of SMG templates that can be used to interpret other SMG observations. To put the ALESS SMGs into context, we compare their stellar masses and SFRs with those of less actively star-forming galaxies at the same redshifts. We find that at z similar or equal to 2, about half of the SMGs lie above the star-forming main sequence (with SFRs three times larger than normal galaxies of the same stellar mass), while half are consistent with being at the high-mass end of the main sequence. At higher redshifts (z similar or equal to 3.5), the SMGs tend to have higher SFRs and stellar masses, but the fraction of SMGs that lie significantly above the main sequence decreases to less than a third.