We present the discovery of five millisecond pulsars (MSPs) from the PALFA Galactic plane survey using Arecibo. Four of these (PSRs J0557+1551, J1850+0244, J1902+0300, and J1943+2210) are binary pulsars whose companions are likely white dwarfs, and one (PSR J1905+0453) is isolated. Phase-coherent timing solutions, ranging from $sim$1 to $sim$3 years in length, and based on observations from the Jodrell Bank and Arecibo telescopes, provide precise determinations of spin, orbital, and astrometric parameters. All five pulsars have large dispersion measures ($>100$ pc cm$^{-3}$, within the top 20% of all known Galactic field MSPs) and are faint (1.4 GHz flux density < 0.1 mJy, within the faintest 5% of all known Galactic field MSPs), illustrating PALFAs ability to find increasingly faint, distant MSPs in the Galactic plane. In particular, PSR J1850+0244 has a dispersion measure of 540 pc cm$^{-3}$, the highest of all known MSPs. Such distant, faint MSPs are important input for accurately modeling the total Galactic MSP population.