A mechanism for crystal-crystal phase transformations (PTs) via surface-induced virtual premelting is justified thermodynamically and confirmed experimentally for the PTs in PbTiO3 nanofibers. When the thickness of the surface melt (which appears much below the melting temperature, especially for nano-objects) exceeds the size of the critical product nucleus, nucleation and growth of the product crystal occur. For nanowires, premelting starts near the smallest size, and hydrodynamic flow driven by reduction in the external surface leads to a large change in shape and further promotion of crystal-crystal PT. During the product crystal-growth stage, virtual melting is observed experimentally within the crystal-crystal interface.