Introduction: Synthetic vascular grafts have been widely used in clinical practice for aortic replacement surgery. Despite their high rates of surgical success, they remain significantly less compliant than the native aorta, resulting in a phenomenon called compliance mismatch. This incompatibility of elastic properties may cause serious post-operative complications, including hypertension and myocardial hypertrophy. Methods: To mitigate the risk for these complications, we designed a multi-layer compliance-matching stent-graft, that we optimized computationally using finite element analysis, and subsequently evaluated in vitro. Results: We found that our compliance-matching grafts attained the distensibility of healthy human aortas, including those of young adults, thereby significantly exceeding the distensibility of gold-standard grafts. The compliant grafts maintained their properties in a wide range of conditions that are expected after the implantation. Furthermore, the computational model predicted the graft radius with enough accuracy to allow computational optimization to be performed effectively. Conclusion: Compliance-matching grafts may offer a valuable improvement over existing prostheses and they could potentially mitigate the risk for post-operative complications attributed to excessive graft stiffness.