We have discovered five millisecond pulsars (MSPs) in a survey of 14 unidentified Fermi Large Area Telescope sources in the southern sky using the Parkes radio telescope. PSRs J0101-6422, J1514-4946, and J1902-5105 reside in binaries, while PSRs J1658-5324 and J1747-4036 are isolated. Using an ephemeris derived from timing observations of PSR J0101-6422 (P = 2.57 ms, DM = 12 pc cm super(-3)), we have detected gamma -ray pulsations and measured its proper motion. Its gamma -ray spectrum (a power law of Gamma = 0.9 with a cutoff at 1.6 GeV) and efficiency are typical of other MSPs, but its radio and gamma -ray light curves challenge simple geometric models of emission. The high success rate of this survey-enabled by selecting gamma -ray sources based on their detailed spectral characteristics-and other similarly successful searches indicate that a substantial fraction of the local population of MSPs may soon be known.