A water-stable solid electrolyte is a key material without which aqueous lithium–air batteries could not be operated. In this study, we have examined the electrical conductivity and mechanical properties of a water-stable lithium-ion-conducting solid electrolyte, Li1+xAlxGeyTi2−x−y(PO4)3 with the NASICON-type structure, as a function of the Al and Ge content. Li1+xAlxGeyTi2−x−y(PO4)3 was synthesized by the conventional solid-state reaction method. The highest lithium-ion conductivity of 1.0 × 10−3 S cm−1 at 25°C and the highest three-point bending strength of 90 N mm−2 at room temperature were observed for a pellet of Li1.45Al0.45Ge0.2Ti1.35(PO4)3 sintered at 900°C.