The recent invention of cold sintering process (CSP) suggests a new opportunity to densify ceramic solid electrolytes at reduced temperatures. In the study, Na3.256Mg0.128Zr1.872Si2PO12 (Mg-doped NASICON) specimens were cold-sintered at 140 °C to ∼83% of the theoretical density. In addition, post-CSP annealing, at temperatures lower than that is needed for the conventional sintering of NASICON, can substantially increase the ionic conductivity (with or without significant further densification). For example, the conductivity of cold-sintered Mg-doped NASICON reached >0.5 mS/cm after annealing at (as low as) 800 °C; in comparison, a dry-pressed specimen exhibited virtually no densification at a higher temperature of 1000 °C with <0.1 mS/cm conductivity. Moreover, a high conductivity of ∼1.36 mS/cm has been achieved for a Mg-doped NASICON cold-sintered and subsequently annealed at 1100 °C (doubling the conductivity of a dry-pressed specimen sintered at the identical condition). Further mechanistic studies showed that annealing at 800–1100 °C increased the grain boundary (GB) conductivities of cold-sintered specimens. The CSP opens a new window to sinter the “thermally-fragile” ceramic solid electrolytes (such as phosphates and sulfates). In addition, it not only provides energy and cost savings but also enables new fabrication routes to make solid-state batteries.