This article is concerned with shape optimization of structures made of a material obeying Hencky's laws of plasticity, with the stress bound expressed by the von Mises effective stress. The ill-posedness of the model is circumvented by using two regularized versions of the mechanical problem. The first one is the classical Perzyna formulation which is regularized, and the second one is a new regularized formulation proposed for the von Mises criterion. Shape gradients are calculated thanks to the adjoint method. The optimal shape is numerically computed by using the level set method. To illustrate the validity of the method, 2D examples are performed.