Cardiovascular stents have been used since the 1990s to treat atherosclerosis, one of leading causes of death in the western world, and structural optimization has led to significant improvements in stent performance. Much of the potential variation in stent geometry, however, has remained unconsidered. This paper presents a non-uniform rational basis spline (NURBS) parameterization of a stent, the inclusion of structural fatigue resistance as a design consideration, and the results of a design optimization based on response surface techniques. Results show the feasibility and merits of the NURBS approach, which models a much broader range of shapes than was previously possible. Multi-objective optimization produces a range of geometrically diverse Pareto-optimal designs; these can be used to develop future clinical design guides, accounting for the variation observed across patients. We conclude by motivating future work with increasingly complex physical modeling and optimization capabilities.