This paper presents a new algorithm that enables the refinement of hexahedral elements while maintaining the appropriate connectivity. In the algorithm, at first the regions of mesh to be refined are defined and, then, the zero-thickness element layers are inserted into the interfaces between the regions. All the meshes in the regions, in which the zero-thickness layers are inserted, are to be regularized in order to improve the shape of the slender elements on the interfaces. This algorithm is applied to the analysis of plastic deformation process. The results show that the refined mesh gives smaller relative errors than the original mesh.