Auto-tune was already a well-established studio tool by the time “Believe” came out, though it was unknown outside the music industry.
Before “Believe,” Auto-tune was used for its intended purpose: to correct vocal performances in a natural-sounding, transparent way. Cher’s producers Mark Taylor and Brian Rawling discovered that if they turned the Retune Speed setting to zero, it produced the futuristic robot sound we’ve all come to know well. Since they were producing a high-tech dance track, they figured that the robot sound fit the mood, so they kept it in.
I doubt that Taylor and Rawling were the first people to discover the zero retune speed setting, but they were the first to use it on a mass-market commercial recording. To keep other people from imitating the sound, they told interviewers that they had achieved the effect with a vocoder. The music press repeated their story endlessly, so to this day there’s widespread confusion about the difference between vocoder and Auto-tune.