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.57ms, DM = 12pccm -3), we have detected γ-ray pulsations and measured its proper motion. Its γ-ray spectrum (a power law of Γ = 0.9 with a cutoff at 1.6GeV) and efficiency are typical of other MSPs, but its radio and γ-ray light curves challenge simple geometric models of emission. The high success rate of this survey - enabled by selecting γ-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. © 2012 The American Astronomical Society. All rights reserved.