Topological band-insulators (TBIs) are bulk insulating materials, which in the presence of time-reversal symmetry feature topologically protected metallic states on their surface or edge. They have recently been discovered in two- and three-dimensional materials with a strong spin-orbit coupling. These unusual states of quantum matter may host Majorana fermions and provide the condensed-matter realization of the exotic theta-vacuum. The existing classification of TBIs departs from time-reversal symmetry, but the role of the crystal-lattice symmetries in the physics of these topological states has remained elusive. Here we provide the classification of TBIs protected not only by time-reversal, but also by crystalline symmetries. We find three broad classes of topological states: Γ states robust against general time-reversal invariant perturbations; translationally active states protected from elastic scattering, but susceptible to topological crystalline disorder; valley topological insulators sensitive to the effects of non-topological and crystalline disorder. These three classes give rise to 18 different two-dimensional, and, at least 70 three-dimensional TBIs, opening up a route for the systematic search for new types of TBIs. © 2013 Macmillan Publishers Limited. All rights reserved.