O sobrenome Anhaia, também grafado Anaia, tem, segundo José Pedro Machado (Dicionário Onomástico Etimológico), origem na palavra basca anai(a), «irmão», por intermédio do castelhano. Contudo, observa Machado:

«Parece [...] que alguns destes apelidos são de origem toponímica, também castelhana: há Anaya em Segóvia e Salamanca; daí aparecerem por vezes com a preposição de: d'Anaia, d'Anhaia. Por confusão, surgiram da Naia, da Nhaia e daqui os apelidos Naia e Nhaia [...]. Hoje Naya também na Galiza [...]. Hoje há em português Anaia e Naia [...].»

Machado acrescenta que encontra Anhaia registado só no Vocabulário da Língua Portuguesa, de Rebelo Gonçalves. É caso para dizer que talvez o ilustre lexicógrafo se tivesse esquecido de pesquisar no Brasil.