We first present a new type of large-scale computational screening approach for identifying promising candidate materials for solid state electrolytes for lithium ion batteries that is capable of screening all known lithium containing solids. We first screen 12,831 lithium containing crystalline solids for those with high structural and chemical stability, low electronic conductivity, and low cost. We then develop a data-driven ionic conductivity classification model using logistic regression for identifying which candidate structures are likely to exhibit fast lithium conduction based on experimental measurements reported in the literature. The screening reduces the list of candidate materials from 12,831 down to 21 structures that show promise as electrolytes, few of which have been examined experimentally. We then employ Density Functional Theory (DFT) molecular dynamics simulations to compute ionic conductivity in these promising candidate materials and others, discovering many new crystalline solid materials with DFT-predicted fast single crystal Li ion conductivity at room temperature. When compared to a random search of materials space, we find that a search over the materials identified by our machine learning-based ionic conductivity model is 2.7 times more likely to identify fast Li ion conductors, with at least a 44 times improvement in the log-average of room temperature Li ion conductivity. We then perform an in-depth study of a new solid-state Li-ion electrolyte material emerging from this screening process that is predicted to exhibit extraordinarily fast ionic conductivity, wide electrochemical stability, low cost, and low mass density: materials from the crystalline lithium-boron-sulfur (LBS) system, including Li5B7S13, Li2B2S5 and Li3BS3. We compute the DFT-based single crystal room temperature ionic conductivity of these three phases to be 74, 10, and 2 mS/cm, respectively, and the thermodynamic electrochemical stability window widths of these materials to be 0.50, 0.16, and 0.45 V, respectively. However, we predict that electrolyte materials synthesized from a range of compositions in Li-B-S system may exhibit even wider thermodynamic electrochemical stability windows of 0.6 V and possibly as high as 3 V or greater. We predict the range of optimal boron-to-sulfur ratios for achieving high ionic conductivity over an electrochemical stability window wider than 0.5 V range to be 1:2 to 1:2.5. The Li-B-S phase mixtures within this range of compositions also have low elemental cost of approximately 0.05 USD/m2 per 10 μm thickness with a mass density below 2 g/cc. Finally, we combine our models with existing models of solid electrolyte performance to find new evidence to suggest that optimization of the sulfides for fast ionic conductivity and wide electrochemical stability may be more likely than optimization of the oxides, and that the oft-overlooked chlorides and bromides may be particularly promising families for Li-ion electrolytes. We also find that the nitrides and phosphides appear to be the most promising material families for electrolytes stable against Li-metal anodes. Furthermore, the spread of the existing data in performance space suggests that fast conducting materials that are stable against both Li metal and a > 4V cathode are exceedingly rare, and that a multiple-electrolyte architecture is a more likely path to successfully realizing a solid-state Li metal battery by approximately an order of magnitude or more.