The primary disadvantage of current design techniques for model predictive control (MPC) is their inability to deal explicitly with plant model uncertainty. In this paper, we present a new approach for robust MPC synthesis that allows explicit incorporation of the description of plant uncertainty in the problem formulation The uncertainty is expressed in both the time and frequency domains. The goal is to design, at each time step, a state-feedback control law that minimizes a ’worst-case’ infinite horizon objective function, subject to constraints on the control input and plant output. Using standard techniques, the problem of minimizing an upper bound on the ’worst-case’ objective function, subject to input and output constraints, is reduced to a convex optimization involving linear matrix inequalities (LMIs). It is shown that the feasible receding horizon state-feedback control design robustly stabilizes the set of uncertain plants. Several extensions, such as application to systems with time delays, problems involving constant set-point tracking, trajectory tracking and disturbance rejection, which follow naturally from our formulation, are discussed. The controller design is illustrated with two examples.