All-solid-state batteries continue to grow as an alternative to replace the traditional liquid-based ones not only because they provide increased safety but also higher power and energy densities. However, current solid-state electrolytes are either ceramics that are brittle but highly conducting (e.g. Li0.33La0.55TiO3, LLTO) or polymer electrolytes that are poorly conducting but form flexible films with desired mechanical properties (e.g. Poly(ethylene oxide):Lithium bis(trifluoromethanesulfonyl)imide, PEO:LiTFSI). In this work, we have developed quaternary composite solid-state electrolytes (CSEs) to combine the benefits of the two types along with Succinonitrile (SN) as a solid plasticizer. CSEs with different compositions have been fully characterized over the whole compositional range. Guided by neural network simulation results it has been found that a polymer-rich CSE film gives the optimal ionic conductivity (>10−3 S cm−1 at 55 °C) and mechanical properties (Tensile strength of 16.1 MPa; Elongation-at-break of 2360%). Our solid-state coin-type cell which employs our in-house made cathode shows good cycling performance at C/20 and 55 °C maintaining specific discharge capacity at 143.2 mAh g−1 after 30 cycles. This new approach of formulating quaternary CSEs is proven to give the best combination of properties and should be universal and be applied to other CSEs with different chemistry.