A new processing method, equal channel angular pressing (ECAP) plus cold rolling (CR), was applied to producing ultra-fine grained FeCoV alloy. The microstructures of ultra-fine grained FeCoV alloy after ECAP, ECAP plus CR, and the effect of tempering treatment on the microstructure of FeCoV alloy produced by ECAP plus CR were investigated. The results show that an elongated substructure with a width of about 0.3 μm is obtained after four-pass ECAP using Route A. Cold rolling after ECAP cannot change the morphologies of elongated substructure, and it results in higher fraction of high-angle boundaries and higher dislocation density compared with the identical ECAP without rolling. Subsequent tempering for 30 min at 853 K brings about many nano-phases precipitating at subgrain boundaries and insides the grains, and the size of precipitated phase is measured to be about 10 nm. Nano-phases grow up with increasing tempering temperature and equiaxed structure forms at 883 K.