A 36mass% Ni austenitic steel was deformed to equivalent strains of 0.8 to 4.8 by the accumulative roll-bonding (ARB) process at 500°C, with slight lubrication. We analyzed the microstructure and crystallographic analysis by employing the electron back-scatter pattern (EBSP) technique in a field emission gun (FEG) SEM. After several ARB cycles, ultrafine lamellar boundary structures elongated in the rolling direction (RD) formed uniformly in the material. Observations indicated that the mean spacing of high-angle lamellar boundaries determined from the EBSP results decreased exponentially as a function of equivalent strain. The fraction of high-angle boundaries (HABs) increased, thus the average misorientation of the boundaries increased with increasing strain. In the six-cycle ARB-processed specimen, the mean spacing of the uniform lamellar boundaries was 150 nm, the fraction of HABs was 75%, and the average misorientation was 32°. The ultrafine lamellar boundary structure in the 36%Ni austenitic steel was finer and straighter than in ferritic steel (IF steel) deformed under similar conditions, probably because recovery occurs more easily in ferritic steel than austenitic steel.