In this paper we give a realization of crystal bases for quantum affine algebras using some new combinatorial objects which we call the Young walls. The Young walls consist of colored blocks with various shapes that are built on a given ground-state wall and can be viewed as generalizations of Young diagrams. The rules for building Young walls and the action of Kashiwara operators are given explicitly in terms of combinatorics of Young walls. The crystal graph of a basic representation is characterized as the set of all reduced proper Young walls. The character of a basic representation can be computed easily by counting the number of colored blocks that have been added to the ground-state wall.

2000 Mathematical Subject Classification: 17B37, 17B65, 81R50, 82B23.