 <p>The two standard patterns for High Availability NAT are:</p> <ul> <li><a href="https://aws.amazon.com/articles/2781451301784570" rel="nofollow">High Availability for Amazon VPC NAT Instances: An Example</a></li> <li><a href="https://aws.amazon.com/articles/5995712515781075" rel="nofollow">Using Squid Proxy Instances for Web Service Access in Amazon VPC: An Example</a> (Uses proxies instead of route tables, I think)</li> </ul> <p>If you are using the NAT for traffic to Amazon S3, you can also take advantage of <a href="https://aws.amazon.com/blogs/aws/new-vpc-endpoint-for-amazon-s3/" rel="nofollow">VPC Endpoint for S3</a> to reduce the reliance on having a HA NAT.</p>