Oxide-ion conductors are essential for clean energy applications such as solid oxide fuel cells (SOFCs). Since the Rb+ ion is the second largest available cation, some Rb-containing oxides are expected to have low activation energy for oxide-ion conductivity and high oxide-ion conductivity at low temperatures. However, the Rb-containing oxide-ion conductors are very rare. Herein, we report the high oxide-ion conductivity of the palmierite-type Rb5BiMo4O16 (e.g., 2.3 mS cm–1 at 560 °C), which was discovered by a combined technique of the computer screening through bond-valence-based energy calculations of 475 compositions of Rb-containing oxides, synthesis, and characterization of the structural and transport properties. Rb5BiMo4O16 exhibits a high oxide-ion conductivity of 0.14 mS cm–1 at 300 °C, which is 29 times higher than that of yttria-stabilized zirconia (YSZ) at 300 °C and comparable to the leading oxide-ion conductors with tetrahedral moieties. The high ionic conductivity below 480 °C is mainly due to the low activation energy for ionic conductivity, which can be attributed to the large free volume of Rb5BiMo4O16. The extremely large anisotropic thermal motion of oxygen atoms and the rotational motion of MoO4 tetrahedra are also responsible for the high conductivity. Rb5BiMo4O16 is stable at high temperatures under CO2 flow, under wet air flow, and under wet 5% H2 in N2 flow, and at about 21 °C in water. Rb5RMo4O16 materials (R: La, Pr, Nd, Sm, Gd, Tb, Er) also exhibit significant conductivity. The discovery of Rb-containing oxides with high conductivity and high stability would open a new avenue of oxide-ion conductors.