It's a bit of a stretch. Their website (http://www.seomoz.org/about) lists a co-founder's traditional marketing company, founded in 1981, as an SEOmoz precursor. But Rand Fishkin, who largely drove the SEO direction that's become successful, didn't join until 1999, and SEOmoz itself was founded in 2004. So it'd make more sense imo to say it's been in business for around 10 years, though one of the co-founders had previously had 20 years' experience running a different (non-SEO) marketing company.