We present 9 new tunes of the pT-ordered shower and underlying-event model in PYTHIA 6.4. These "Perugia" tunes update and supersede the older "S0" family. The data sets used to constrain the models include hadronic Z0 decays at LEP, Tevatron minimum-bias data at 630, 1800, and 1960 GeV, Tevatron Drell-Yan data at 1800 and 1960 GeV, and SPS min-bias data at 200, 546, and 900 GeV. In addition to the central parameter set, called "Perugia 0", we introduce a set of 8 related "Perugia Variations" that attempt to systematically explore soft, hard, parton density, and colour structure variations in the theoretical parameters. Based on these variations, a best-guess prediction of the charged track multiplicity in inelastic, nondiffractive minimum-bias events at the LHC is made. Note that these tunes can only be used with PYTHIA 6, not with PYTHIA 8. Note: this report was updated in March 2011 with a new set of variations, collectively labeled "Perugia 2011", that are optimized for matching applications and which also take into account some lessons from the early LHC data. In order not to break the original text, these are described separately in Appendix B.