In this paper, we develop a shape design optimization method for thermo-elastoplasticity problems that is applicable to the welding or thermal deformation problems of ship structures. Shell elements and a programming language APDL in a commercial finite element analysis code, ANSYS, are employed in the shape optimization. The point of developed method is to determine the design parameters such that the deformed shape after welding fits very well to a desired design. The geometric parameters of surfaces are selected as the design parameters. The modified method of feasible direction (MMFD) and finite difference sensitivity are used for the optimization algorithm. Two numerical examples demonstrate that the developed shape design method is applicable to existing hull structures and effective for the structural design of ships.