Recently, there has been significant interest in developing solid-state lithium ion electrolytes for use in batteries and related technologies. We have used first-principles modeling techniques based on density functional theory and the nudged elastic band method to examine possible Li ion diffusion mechanisms in idealized crystals of the electrolyte material Li3PO4 in both the γ and β crystalline forms, considering both vacancy and interstitial processes to find the migration energies Em. We find that interstitial diffusion via an interstitialcy mechanism involving the concerted motion of an interstitial Li ion and a neighboring lattice Li ion may provide the most efficient ion transport in Li3PO4. Ion transport in undoped crystals depends on the formation of vacancy-interstitial pairs requiring an additional energy Ef, which results in a thermal activation energy EA=Em+Ef/2. The calculated values of EA are in excellent agreement with single crystal measurements on γ-Li3PO4. Our results examine the similarities and differences between the diffusion processes in the γ and β crystal structures. In addition, we analyze the zone center phonon modes in both crystals in order to further validate our calculations with experimental measurements and to determine the range of vibrational frequencies associated with Li ion motions which might contribute to the diffusion processes.