We revisit Steffen’s known flexible polyhedron, originally described in 1978, and investigate whether we can increase its range of motion by varying his original dimensions. We also define the regularity of a polyhedron. Using a simulated annealing algorithm, we perform multi-objective optimization on the Steffen polyhedron to achieve both maximum regularity and range of motion. The results show that we are able to both increase the range of motion possible for the polyhedron, while still making the polyhedron more regular.