The authors present variational formulations of the problem on unilateral contact between elastic bodies with nonlinear surface Winkler layers in the form of nonquadratic variational inequality, and a nonlinear variational equation. Existence and uniqueness of solutions for these variational problems are investigated. To solve the nonlinear variational equation corresponding to the original contact problem, a class of parallel iterative methods of domain decomposition is proposed. Each step of these methods comprises a parallel solution of linear variational equations in separate bodies, which are equivalent, in a weak sense, to linear elasticity problems with boundary Robin conditions on possible contact zones. The proposed methods are investigated numerically by finite element approximations.