Electrospinning provides a simple approach to fabricating nanofibers and assemblies with controllable hierarchical structures. In this communication, we demonstrate that electrospinning can be combined with calcination to further maneuver the morphology and phase structure of nanofibers. More specifically, single-crystal V2O5 nanorods could be grown on rutile nanofibers by carefully calcining composite nanofibers consisting of amorphous V2O5, amorphous TiO2, and poly(vinylpyrrolidone). The size of the resulting V2O5 nanorods could be conveniently controlled by varying the composition of the nanofibers and/or the calcination temperature. In addition to the nanorod-on-nanofiber hierarchical structure, we believe this approach can also be extended to fabricate other more complex architectures.