Solid-state electrolytes with high ionic conductivities, great flexibility, and easy processability are needed for high-performance solid-state rechargeable lithium batteries. In this work, we synthesize nanosized cubic Li6.25Al0.25La3Zr2O12 (LLZO) by solution combustion method and develop a flexible garnet-based composite solid electrolyte composed of LLZO, poly(ethylene carbonate) (PEC), poly(vinylidene fluoride-hexafluoropropylene) (P(VdF-HFP) and lithium bis(fluorosulfonyl)imide (LiFSI)). In the flexible composite solid electrolytes, LLZO nanoparticles, as ceramic matrix, have a positive effect on ionic conductivities and lithium ion transference number (t Li+). PEC, as a fast ion-conducting polymer, possesses high t Li+ inherently. P(VdF-HFP), as a binder, can strengthen mechanical properties. Consequently, the as-prepared composite solid electrolyte demonstrates high t Li+ (0.82) and superb thermal stability (remaining LLZO matrix after burning). All-solid-state LiFePO4|Li cells assembled with the flexible composite solid electrolyte deliver a high initial discharge specific capacity of 121.4 mAh g−1 and good cycling stability at 55 °C.