Solid state electrolytes (SSEs) with fast Li conductivity can significantly improve Li ion accumulators in terms of electrochemical efficiency, thermal and mechanical stability, and environmental compatibility. Compounds crystallizing in the structure of NaZr2(PO4)3 (NZP) are regarded as promising SSEs, mainly because of their three-dimensional network of migration channels. Starting from LiTi2(PO4)3, we analyzed a large variety of NZP-type materials by systematically screening the relevant parts of the periodic table, replacing Ti fully and partly by tri-, tetra-, and pentavalent cations, and the phosphate by silicate, vanadate, and arsenate anions. The influence of different elements on preferred Li sites, Li mobility, and possible migration paths were analyzed by means of a combination of computational methods, ranging from density functional theory to molecular dynamics simulations with ionic bond valence potentials. Minimum energy paths and migration barriers were identified by nudged-elastic-band and energy-lanscape-mapping calculations.