They’ve been an advertising company since 2000, so I’d argue that yes it was there, people just didn’t recognise it/gave them the benefit of the doubt.
AdSubtract advertised it's ability to block doubleclick.com cookies in March of 2000: https://www.computerworld.com.au/article/91102/adsubtract_bl...
The article also mentions Siemens' WebWasher product which blocked cookies. Other cookie-blocking products were released in the same time period.
at that time Google was the good guy serving up only text ads.