A fundamental open problem in condensed-matter physics is how the dichotomy between conventional and topological band insulators is modified in the presence of strong electron interactions. We show that there are six interacting electronic topological insulators that have no noninteracting counterpart. Combined with the previously known band insulators, these produce a total of eight topologically distinct phases. Two of the six interacting topological insulators can be described as Mott insulators in which the electron spins form spin analogs of the topological band insulator. The remaining phases are obtained as combinations of these two "topological paramagnets" and the topological band insulator. We prove that these eight phases form a complete list of all possible interacting topological insulators and discuss their experimental signatures.