This paper develops two-step methods for solving contact problems with uncertainties. In the first step, we propose stochastic Lagrangian multiplier/penalty methods to compute a set of reduced basis. In the stochastic Lagrangian multiplier method, the stochastic solution is represented as a sum of products of a set of random variables and deterministic vectors. In the stochastic penalty method, the problem is divided into the solutions of non-contact and possible contact nodes, which are represented as sums of the products of two different sets of random variables and deterministic vectors, respectively. The original problems are then transformed into deterministic finite element equations and one-dimensional (corresponding to stochastic Lagrangian multiplier method)/two-dimensional (corresponding to stochastic penalty method) stochastic algebraic equations. The deterministic finite element equations are solved by existing numerical techniques, and the one-/two-dimensional stochastic algebraic equations are solved by a sampling method. Since the computational cost for solving stochastic algebraic equations does not increase dramatically as the stochastic dimension increases, the proposed methods avoid the curse of dimensionality in high-dimensional problems. Based on the reduced basis, we propose semi-reduced order Lagrangian multiplier/penalty equations with two components in the second step. One component is a reduced order equation obtained by smooth solutions of the reduced basis and the other is the full order equation for the nonsmooth solutions. A significant amount of computational cost is saved since the sizes of the semi-reduced order equations are usually small. Numerical examples of up to 100 dimensions demonstrate the good performance of the proposed methods.