Ultra-low carbon IF steel was deformed to various strains ranging from 0.8 to 5.6 by the accumulative roll-bonding (ARB) process at 500°C, and subsequently annealed at various temperatures for 1.8 ks in order to clarify the effect of strain on the microstructures and mechanical properties. The materials deformed by relatively low strains below 2.4 revealed dislocation cell or subgrain structures including small number of deformation induced high-angle grain boundaries. The microstructural change in these materials during annealing was understood in terms of discontinuous recrystallization characterized by nucleation and growth. The materials severely strained over 4.0, on the other hand, were filled with the pancake-shaped ultra-fine grains surrounded by high-angle grain boundaries. The mean thickness and length of the pancake-shaped ultra-fine grains were about 200 nm and 900 nm, respectively. The specimens ARB processed above strain of 4.0 performed very high strength up to 900 MPa, though they showed limited elongation. Normal grain growth with recovery at grain interior occurred during annealing of the highly strained materials, because all the boundaries surrounding the ultra-fine grains had equivalent degree of mobility. The 0.2% proof stress of the specimens having various grain sizes held Hall-petch relationship. It was also clarified that high-angle boundaries could contribute more greatly to the strength than low-angle boundaries. In contrast, the uniform elongation of the ultra-fine grained materials whose mean grain sizes were smaller than 1 μm suddenly decreased to about a few percents because of the early plastic instability. It was concluded from the present study that strain over 4.0 is necessary to obtain uniform ultra-fine grains having high strength.