The link between chemical orbitals described by local degrees of freedom and band theory, which is defined in momentum space, was proposed by Zak several decades ago for spinless systems with and without time-reversal in his theory of elementary band representations. In Nature 547, 298-305 (2017), we introduced the generalization of this theory to the experimentally relevant situation of spin-orbit coupled systems with time-reversal symmetry and proved that all bands that do not transform as band representations are topological. Here, we give the full details of this construction. We prove that elementary band representations are either connected as bands in the Brillouin zone and are described by localized Wannier orbitals respecting the symmetries of the lattice (including time-reversal when applicable), or, if disconnected, describe topological insulators. We then show how to generate a band representation from a particular Wyckoff position and determine which Wyckoff positions generate elementary band representations for all space groups. This theory applies to spinful and spinless systems, in all dimensions, with and without time reversal. We introduce a homotopic notion of equivalence and show that it results in a finer classification of topological phases than approaches based only on the symmetry of wavefunctions at special points in the Brillouin zone. Utilizing a mapping of the band connectivity into a graph theory problem, which we introduced in Nature 547, 298-305 (2017), we show in companion papers which Wyckoff positions can generate disconnected elementary band representations, furnishing a natural avenue for a systematic materials search.