I de tre årtusinder føraztekerne ankom i1436, var de mest magtfulde og indflydelsesrige grupper i hvad der i dag er Oaxaca, zapotekerne, mixtekerne og mixerne. Den civilisation disse grupper opnåede, kan ses på vigtige arkæologiske steder somMonte Albán,Mitla, Cerro de Minas, Guiengola og Huijatzoo.
Da aztekerne slog sig ned ved Cerro del Fortín og ned til den nuværende Carmen Alto-kirke, hvor deres tempel lå, ændrede indflydelsen sig. Statens navn kommer af dennahuatl-betegnelse, aztekerne gav den centrale del rundt om hovedstaden,Huaxyácac eller stedet med huaje-træerne, på grund af det store antal leucaena-sorter.
Daspanierne ankom mindre end et århundrede senere, syntes de det var svært at udtale og navnet endte med at blive det nutidige Oaxaca, som navn på både byen og staten. Den bosættelse som spanierne grundlagde med navnetSegura de la Frontera, senere kendt somNueva Antequera, blev officielt ophøjet til en royal by i 1532 efter dekret fra kejserCarlos V, som gav byen navnetAntequera de Guaxaca.
