Abstract: This study is to formulate a stress-updating method when solving static equilibrium equations of finite element models of structures with strain-history dependent material (SHDM). Using the dynamic relaxation method (DRM), the nonlinear-elastic-increment algorithm was employed so that the loading and unloading paths were fixed within one increment and the material became nonlinear elastic within the increment. The algorithm eliminated the fictitious strain history from the iterative series including the final converged solution. Moreover, this method removed the limitation whereby the accuracy of the solution was dependent upon the increment step size. Three numerical examples were used to verify the proposed algorithm. It is expected that the algorithm promotes the development of DRM for solving static problems of nonlinear finite element analyses of SHDM structures.