Nanocrystalline materials often exhibit extraordinary mechanical and physical properties but their applications at elevated temperatures are impaired by the rapid grain growth. Moreover, the grain growth in nanocrystalline oxide nanofibers at high temperatures can occur at hundreds of degrees lower than that would occur in corresponding bulk nanocrystalline materials, which would eventually break the fibers. Herein, by characterizing a model system of scandia-stabilized zirconia using hot-stage in situ scanning transmission electron microscopy, we discover that the enhanced grain growth in nanofibers is initiated at the surface. Subsequently, we demonstrate that coating the fibers with nanometer-thick amorphous alumina layer can enhance their temperature stability by nearly 400 °C via suppressing the surface-initiated grain growth. Such a strategy can be effectively applied to other oxide nanofibers, such as samarium-doped ceria, yttrium-stabilized zirconia, and lanthanum molybdate. The nanocoatings also increase the flexibility of the oxide nanofibers and stabilize the high-temperature phases that have 10 times higher ionic conductivity. This study provides new insights into the surface-initiated grain growth in nanocrystalline oxide nanofibers and develops a facile yet innovative strategy to improve the high-temperature stability of nanofibers for a broad range of applications.