The organic electrolytes of most current commercial rechargeable Li-ion batteries (LiBs) are flammable, toxic, and have limited electrochemical energy windows. All-solid-state battery technology promises improved safety, cycling performance, electrochemical stability, and possibility of device miniaturization and enables a number of breakthrough technologies towards the development of new high power and energy density microbatteries for electronics with low processing cost, solid oxide fuel cells, electrochromic devices, etc. Currently, rational materials design is attracting significant attention, which has resulted in a strong demand for methodologies that can accelerate the design of materials with tailored properties; cheminformatics can be considered as an efficient tool in this respect. This study was focused on several aspects: (i) identification of the parameters responsible for high Li-ion conductivity in garnet structured oxides; (ii) development of quantitative models to elucidate composition-structure-Li ionic conductivity relationships, taking into account the experimental details of sample preparation; (iii) circumscription of the materials space of solid garnet-type electrolytes, which is attractive for virtual screening. Several candidate compounds have been recommended for synthesis as potential solid state electrolyte materials.