Was Cher's Believe the first production to use auto-tune as a noticeable effect? Yes, at least in mainstream big-production music.
Was Cher's Believe the first production to use auto-tune at all? Evidence strongly suggests that it was not, but there's no info available regarding who and when.
It's not easy to dive into the very beginning of auto-tune history, since the process was being hidden from the public. There were many reasons behind this, including "trade secret" (you don't want your competition to have this new process in their hands), and the fear that automatic pitch correction would be seen as foul play (which ended up happening, and still is a source of hot debate). Believe producers claimed for years that they were using a Digitech Talker vocoder pedal.
From a 1999 Sound on Sound article:
Cher's 'Believe' (Dec 1998) was the first commercial recording to feature the audible side-effects of Antares Auto-tune software used as a deliberate creative effect. The (now) highly recognisable tonal mangling occurs when the pitch correction speed is set too fast for the audio that it is processing and it became one of the most over-used production effects of the following years.
In February 1999, when this Sound On Sound article was published, the producers of this recording were apparently so keen to maintain their 'trade secret' process that they were willing to attribute the effect to the (then) recently-released Digitech Talker vocoder pedal. As most people are now all-too familiar with the 'Cher effect', as it became known, we have maintained the article in its original form as an interesting historical footnote.
Producers Mark Taylor and Brian Rawling noticed that auto-tune could be used as an effect while working on Believe.
While working with Cher on the song "Believe" in 1998, producers Mark Taylor and Brian Rawling discovered that if they set Auto-Tune on its most aggressive setting, so that it corrected the pitch at the exact moment it received the signal, the result was an unsettlingly robotic tone.
But the process was originally intended to be subtle, to not be noticeable.
Auto-Tunes was designed to be used discretely, and that no one needed to know that any software correction had been applied to vocal tracks. Hildebrand pointed out that there is an extreme setting available in Auto-Tune, the "zero" setting, that is extremely popular and extremely noticeable.
Cher's Believe used it as an effect, where it is obvious and noticeable, but other artists might have been using it before that with settings that would make it harder to notice (if at all).
The production of that disc began in summer of 1998, auto-tune was released in 1997.
Following the success of Infinity, Dr. Andy next turned his attention to the emerging market for software plug-ins. Drawing again on geophysics-based DSP technology, he developed and introduced MDT (Multiband Dynamics Tool), one of the first successful Pro Tools plug-ins. This was followed by JVP (Jupiter Voice Processor), SST (Spectral Shaping Tool) and, in 1997, Auto-Tune, a program that corrected pitch problems in vocals and other solo instruments. Auto-Tune became an instant phenomenon, firmly establishing Antares (as the company had been renamed) as a developer of truly astonishing products using DSP technology. Auto-Tune quickly became the largest-selling audio plug-in of all time.
Between its release in 1997 and Cher's Believe in October 1998, there is almost no info about it. All I can find is that it was a "top secret", which suggests that other productions were using it, but more discretely.
Originally intended to correct any sharp or flat notes from a singer’s recorded performance, Auto-Tune quickly became a top secret hit in the music industry. That was until Cher‘s 1998 smash ‘Believe’ exposed exactly what was going on in recording studios across the world, as Hildebrand confirms.
“The studios didn’t like to talk about what they were doing, in general. I mean, this was in the fall-out of Milli Vanilli. So they didn’t advertise the fact they were fixing the singer’s pitch, but they did, and they all knew what it sounded like if you set that control to zero. She was just the first to make it public,” he explained.
Because all these, production-wise, the historical roots of auto-tune are not well known. We know of the first mainstream productions that used it as an effect, like Eifel 65's Blue (1999) and Daft Punk's One More Time (2000), but productions using it discretely were not being loud about it.