André 3000 comenzó a trabajar en "Hey Ya!" en diciembre de 2002 en los Stankonia Studios (Atlanta, Georgia).