Gordoa procede de Córdoba, nombre de la capital andaluza, según Mitxelena (1969: 36; 1984: 288; AV, p. 246), Gordova en la reja de San Millán de 1025, forma empleada al menos hasta 1518, como puede verse en la documentación, aunque encontramos Gordoa ya para 1470. La sonorización de las oclusivas sordas en posición inicial es habitual en los préstamos, aunque la sonora alterna en muchas palabras con la sorda: bekatu / pekatu 'pecado', biztu / piztu 'encender', kapana / gapana 'cabaña' (esta variante en toponimia, en contadas ocasiones), katea / gatina 'cadena', koroa / goroa 'corona' (esta solo en nombres de lugar), etc. Está claro, de todos modos, que el nombre ha llegado al euskera a través del romance, no directamente del topónimo indígena ni del árabe.

Knörr (1995: 217) dice que Gordoba se emplea todavía en la actualidad. El problema, en este caso, es saber si se trata del mantenimiento de la forma medieval mencionada o de una evolución del tipo Aldaiondoa > Aldaiondoba, Andua > Anduba (Lerga; Salaberri, 1994: 580, 583), Zerkondoa > Zerkondoba (Artajona / Artaxoa, Jimeno y Salaberri, 2018: 150-151) debida a la debilitación y pérdida del euskera y posterior empleo de los topónimos vascos por hablantes de castellano. En la documentación de Santa María de Bujedo aparece «don Ochova de Lecinnana et so fijo Juan Ochova» (1190, Ruiz de Lóizaga, 2000: 108) que, a partir de Otxoa 'Lope', parece presentar el mismo fenómeno, pero en fecha mucho más temprana.

En Navarra tenemos, al lado de la capital, la localidad de Cordovilla, nombre que debería ser escrito con <b>, dado que en realidad no es sino un diminutivo de Córdoba y no tiene nada que ver con villa. En euskera se empleaba Kordoba (escrito también con C- en la documentación oficial; véase Jimeno Jurío, 2011: 120-121), tal como muestran los topónimos Kordobazubia 'el puente de Cordovilla' y Kordobazuloa 'el agujero, el hoyo de Cordovilla' de Ezkirotz (ibid., 211), o Kordobarana 'el valle de Cordovilla', Kordobalarraña 'la era de Cordovilla' de la capital navarra (Jimeno y Salaberri, 2006: 229). Véase este testimonio temprano: «La XIIª peça es en Cordova arana, la quoal parte el/la carrera que va de Cordoviela at Pamplona» (1252, García Larragueta, 1957: 338).

Volviendo al nombre de la localidad alavesa que nos ocupa, hay que señalar que en un par de ocasiones encontramos Gordo en 1488 (Paz Moro, 2013: 239, 250), tal vez porque la -a final se interpretó como artículo.