The term replaces Application Service Provider and can be found in documents dating back to at least early 2001.
Software as a Service (SaaS), commonly referred to as the Application
Service Provider (ASP) model, is heralded by many as the new wave in
application software distribution. Following the maxim that “the
Internet changes everything,” many believe that traditional packaged
desktop and enterprise applications will soon be swept away by the
tide of Web-based, outsourced products and services that remove the
responsibility for installation, maintenance and upgrades from
over-burdened MIS staff. Some analysts and industry members believe
that packaged software, as a separate entity will cease to exist.
While such drastic predictions have not yet happened, due to
technical and business issues, the spirit of this change – the
delivery, management and payment of software as a service rather than
a product – is affecting all participants in the software industry
It appears that the term was non-existent or not widely used before that point. An article from April of 2000 uses ASP.