It may have been the early 2000s, but it was very early on. It "came to a head," on a trip to San Francisco, on one particular project (I am not at liberty to discuss). It would not have been beyond about 2002. I think it was pre 9/11, but my memory of that time is a bit fuzzy. I did a lot of traveling.
I'm pretty sure that HTTPRequest debuted in IE 5 or 6.
The way I remember it is it became widely known once gmail and google maps shocked everyone with its effective use. So that's quite a bit later than 2002. But it's likely that it is just when I noticed, being pretty far removed from web development at the time.
AFAICR, it started in the mid-to-late 90s, although as with all things web in that period, was a non-standard cobbling together of feature and functionality using whatever technologies were available, while browsers themselves lurched in the dark and added features.
It's more akin to saying "We want to do this thing that's never been done on the web before, and no one ever thought to do. How do we assemble it out of this box of scraps that HTML and browsers currently give us?"
Consequently, there was probably proto-AJAX with ActiveX, the early js landscape, and iframes. But it would have certainly depended on where you worked.
Critically, internet connections were much slower (in latency and bandwidth), so partial page loads were more of an advantage.
I'm pretty sure that HTTPRequest debuted in IE 5 or 6.