In a mechanical component, stress-concentration is one of the factors contributing to reduce fatigue life. This paper presents a design methodology based on shape optimization to improve the fatigue safety factor and increase the radial stiffness of Nitinol self-expandable stent-grafts. A planar lattice free of stress concentrators is proposed for the synthesis of a stent with smooth cell shapes. Design optimization is systematically applied to minimize the curvature and reduce the bending strain of the elements defining the lattice cells. A novel cell geometry with improved fatigue life and radial supportive force is introduced for Nitinol self-expandable stent-grafts used for treating abdominal aortic aneurism. A parametric study comparing the optimized stent-graft to recent stent designs demonstrates that the former exhibits a superior anchoring performance and a reduction of the risk of fatigue failure.