Klub powstał w grudniu 2012, kiedy to ogłoszono, że za pół roku do rozgrywek drugiej ligi meksykańskiej dołączy nowa drużyna. Został utworzony na licencji zespołu Club Tecamachalco, który awansował wówczas z trzeciej do drugiej ligi, lecz wobec braku odpowiedniej infrastruktury nie został dopuszczony do rozgrywek. Wobec tego właściciele Tecamachalco zwrócili się z prośbą o wsparcie do władz stanu Oaxaca, który został siedzibą nowej ekipy[1]. Klub został tym samym kolejną ekipą z Oaxacy, po istniejących wcześniej Chapulineros de Oaxaca i Cruz Azul Oaxaca[2]. Nazwę Alebrijes de Oaxaca otrzymał w wyniku powszechnego głosowania[3]. Zespołowi zezwolono na użytkowanie obiektu Estadio Benito Juárez.