For an existing website, the sooner, the better. Because it takes significant time to build a high-quality SEO campaign, a delay in getting started is a delay in getting results.
If, however, you are about to create or launch a brand-new or redesigned website, the best time to implement SEO is prior to launch. Building in features and structure that supports good SEO results is a great investment that can give your new site a head start.