Estimating the Domain of Attraction (DA) of equilibrium points is a problem of fundamental importance in systems engineering. Several approaches have been proposed for the case of known polynomial systems allowing one to find the Largest Estimate of the DA (LEDA) for a given Lyapunov Function (LF). However, the problem of estimating the Robust DA (RDA), that is the DA guaranteed for all possible uncertainties in an uncertain system, it is still an unsolved problem. In this paper, LMI methods are proposed for estimating the RDA in the case of systems depending polynomially in the state and in the uncertainty which is supposed to belong to a polytope. Specifically, the issue of computing the Robust LEDA (RLEDA), that is the intersection of all LEDAs, is considered for common and parameter-dependent Us, providing constant and parameter-dependent lower bounds. The computation of approximations with simple shape of the RLEDA in the case of parameter-dependent Us is also discussed. (C) 2004 Elsevier Ltd. All rights reserved.