Cargando el mapa…
Hay tres hipótesis, ninguna confirmada. Una lo hace venir del árabe an-nahya, «agua estancada», lo que lo relacionaría con topónimos parecidos como Anaya, en Segovia, o Anaya de Huebra, en Salamanca. Esa explicación implica que Anaya no debe relacionarse con otros como Minaya. Otra, señalada por Antonio Llorente Maldonado sin descartar la árabe, apunta a un posible origen vasco-navarro, de anai, «hermano», que con el artículo vasco daría Anaia, «el hermano». Una tercera, también de Llorente Maldonado, parte del árabe al-nahiya, «camino, sendero, vía», que habría dado annaia en árabe vulgar, algo posible porque por Anaya de Alba pasaba la calzada que unía Alba con Piedrahíta.
El pueblo se remonta a la repoblación de los reyes de León en la Edad Media y quedó en el cuarto de Cantalberque de la jurisdicción de Alba de Tormes. Ya en el siglo XIII se llamaba Anaya. Con la creación de las provincias actuales en 1833 pasó a la provincia de Salamanca, y formó parte del partido judicial de Alba de Tormes hasta que este desapareció y se integró en el de Salamanca.