We construct the Lagrangian description of arbitrary integer higher-spin massless fields on the background of the D-dimensional anti-de Sitter space. The operator constraints in auxiliary Fock space corresponding to subsidiary conditions for irreducible unitary, massless representations of the D-dimensional anti-de Sitter group are formulated. Unlike flat space, the algebra of the constraints turns out to be nonlinear and analogous to the W-3 algebra. We construct the nilpotent BRST charge for this nonlinear algebra and derive on its basis the correct field content and gauge invariant action describing the consistent arbitrary integer-spin field dynamics in AdS space. (C) 2001 Elsevier Science B.V. All rights reserved.