I believe that Fray Marcos de Niza was probably the very first explorer (besides the native americans) of what today is Texas and New Mexico. I think that at that time the Real Audencia was a Compostela of Nayarit, Nueva Galicia, Nueva Espana (Mexico).
Reference: GUADALAJARA,5,R.1,N.7
http://pares.mcu.es/ParesBusquedas20/catalogo/description/342302