A small stellated dodecahedron appears in a marble tarsia on the floor of St. Mark's Basilica, Venice, Italy. It dates from the 1400s and is sometimes attributed to Paolo Uccello.

In his Perspectiva corporum regularium (Perspectives of the regular solids), a book of woodcuts published in the 1500s, Wenzel Jamnitzer depicts the great dodecahedron. It is clear from the general arrangement of the book that he regards only the five Platonic solids as regular, and does not understand the regular nature of his great dodecahedron. He also depicts a figure often mistaken for the great stellated dodecahedron, though the triangular surfaces of the arms are not quite coplanar, so it actually has 60 triangular faces.

The Kepler solids were discovered by Johannes Kepler in 1619. He obtained them by stellating the regular convex dodecahedron, for the first time treating it as a surface rather than a solid. He noticed that by extending the edges or faces of the convex dodecahedron until they met again, he could obtain star pentagons. Further, he recognized that these star pentagons are also regular. In this way he found two stellated dodecahedra, the small and the great. Each has the central convex region of each face "hidden" within the interior, with only the triangular arms visible. Kepler's final step was to recognize that these polyhedra fit the definition of regular solids, even though they were not convex, as the traditional Platonic solids were.

In 1809, Louis Poinsot rediscovered these two figures. He also considered star vertices as well as star faces, and so discovered two more regular stars, the great icosahedron and great dodecahedron. Some people call these two the Poinsot solids. Poinsot did not know if he had discovered all the regular star polyhedra.

Three years later, Augustin Cauchy was to prove the list complete, and almost half a century later Bertrand provided a more elegant proof by facetting the Platonic solids.

The Kepler-Poinsot solids were given their English names in the following year, 1859, by Arthur Cayley.

A hundred years later, John Conway developed a systematic terminology for stellations in up to four dimensions. Within this scheme, he suggested slightly modified names for two of the regular star polyhedra. So far, Conway's names have seen some use but have not really caught on.