A polyhedron with V vertices, E edges, and F faces satisfies the relation V-E+F=2. This relationship was first noticed by Euler in 1750 (although a related formula was known to Descartes in 1630). Euler's proof turned out to be flawed. From 1750 to 1850 mathematicians tried to come to grips with this formula. Legendre, Cauchy, Staudt, and others presented new proofs and generalizations. Meanwhile, Lhuilier, Hessel, and Poinsot unveiled exotic "counterexamples." In this talk we present the history of this beloved formula up to the middle of the nineteenth century, while it was still a theorem about polyhedra and before it was recognized as a topological theorem.