Ketika menyinggung tentang kota legendaris yang hilang, semua tidak bisa menghindari tentang kota legenda yang hilang bernama Cibola. Cibola adalah kota legenda yang sangat makmur dan kaya raya. Selama era kolonisasi Spanyol kota itu dikatakan berada di suatu tempat di utara Meksiko, yang sekarang menjadi negara Amerika bagian barat daya.

Legenda pada abad pertengahan mengatakan bahwa kabar tentang kota itu berasal dari bangsa Moor yang menginvansi semenanjung Iberia, dimana berdasarkan cerita tujuh uskup yang melarikan diri ke suatu tempat dan menetap di sebuah tanah yang terletak di sebelah barat dengan menyeberangi lautan.

Penemuan benua Amerika dan desas desus tentang keberadaan kota tersebut membuat Marcos de Niza ingin melakukan pencarian. Dia menganggap bahwa kota tersebut tersembunyi di sana. Legenda menggambarkan Cibola sebagai kota emas yang didirikan oleh tujuh uskup agung yang konon melarikan diri dari semenanjung Iberia ketika tempat mereka jatuh ke tangan bangsa Arab. Dalam sebuah versi mengatakan bahwa para uskup ini adalah orang Portugis yang mengungsi dari kota Oporto dan akhirnya menetap di sebuah pulau jauh terletak di suatu tempat di sebelah barat.

Tanah itu tidak bisa diakses dengan berjalan kaki melainkan hanya dapat ditemukan dengan melintasi lautan. Spanyol mulai menyebarkan versi lain dari legenda itu dimana tujuh uskup tersebut bukanlah orang Portugis tetapi uskup itu asli orang Spanyol dari kota Merida, yang melarikan diri pada tahun 713.

Sembilan tahun setelah para usku ini melarikan diri. Spanyol melakukan penakhlukan yang berakhir pada tahun 1429 ketika raja Katolik Eropa berhasil mengusir bangsa Moor keluar dari Granada, sehingga Spanyol berhasil memulihkan kendali total atas semenanjung Iberia.

Pada tahun 1507, Amerika berhasil diidentifikasikan sebagai benua baru yang terpisah dari Asia. Segera setelah itu, penemuan dan penaklukan Kekaisaran Aztec yang kuat oleh Hernán Cortés menunjukkan keberadaan peradaban yang kaya dan maju di Dunia Baru, yang membangkitkan ambisi banyak penakluk Spanyol lainnya.

Apa yang terjadi setelah penemuan benua Amerika tidak baik bagi penduduk asli di sana. Segera setelah itu, Hernan Cortes mendominasi dunia baru dengan menaklukkan Kekaisaran Aztec yang perkasa, dan pada saat yang sama, dia mengungkapkan kepada orang Eropa bahwa ada peradaban yang sangat kuat dan sangat kaya di Dunia Baru. Kisah-kisah tentang peradaban yang tidak diketahui dan kaya di Amerika, segera membangkitkan minat para penjelajah dan penakluk yang ingin menjejakkan kaki di Benua Amerika, mencari kekayaan yang tak terbatas.

Setelah jatuhnya Meksiko, semakin banyak desas-desus mulai beredar tentang keberadaan suatu tempat yang kaya dan perkasa di belahan utara benua itu. Pencarian itu juga dipicu oleh suku Aztec kuno yang mengklaim bahwa emas yang digunakan untuk mendirikan bangunan berasal dari utara, belum lagi ada mitos tentang asal mereka dari tempat bernama Aztlan yang juga terletak di suatu tempat di utara.

Isu - isu tersebut akhirnya mengarah pada perpaduan antara legenda abad pertengahan dengan sejarah dunia baru, ketika ada ekspedisi Panfilo de Narvaez yang gagal ke Florida tahun 1528, mulai menyebarkan desas-desus di Meksiko tentang dugaan keberadaan kota-kota besar yang terletak di daerah utara.

Seorang pria yang selamat dari insiden kapal karam bernama Alvar Núñez Cabeza de Vaca bercerita tentang perjalanan panjang dirinya yang selamat dari Florida sampai ke pantai Sinaloa dan akhirnya melintasi seluruh benua Amerika. Orang lain yang selamat dari kapal karam tersebut bernama Esteban de Dorantes, yang juga dikenal sebagai Estebanico.

Akhirnya kisah kota emas tersebut menjadi populer di Spanyol. Maka, bangsawan Spanyol yang bernama Antonio de Mendoza, memutuskan untuk mencari kebenaran cerita itu dan menyiapkan sebuah ekspedisi yang dipimpin oleh Marcos de Niza untuk mencari harta di kota yang hilang tersebut. Estebanico yang juga ikut dalam pencarian tersebut melayani sebagai pemandu dan pada beberapa kesempatan, dia melakukan perjalanan mendahului ekspedisi untuk memberi tahu tentang segala sesuatu yang ada di depan mereka.

Dalam satu kesempatan, dia membenarkan bahwa dia telah mendengar kabar tentang kota-kota besar dan kuat di tempat yang disebut Vacapa. Akhirnya, tanpa menemukan kota-kota emas, Estebanico terbunuh oleh penduduk asli Amerika di Hikawuha, New Mexico, yang menyebabkan ekspedisi terhenti.

Namun, Marcos de Niza yakin bahwa kota-kota dan kerajaan yang makmur itu benar-benar ada. Marcos de Niza akhirnya kembali ke Meksiko dengan mengatakan bahwa setelah kematian Estebanico, dia melanjutkan perjalanannya. Dia mengatakan bahwa pada akhirnya, dia telah menyaksikan dengan matanya sendiri, kota yang lebih besar dari kota Tenochtitlan. Di kota megah itu, penduduk asli dihiasi dengan segala macam kekayaan, mereka menggunakan perak dan piring emas, menghias rumah dan kuil mereka dengan mutiara, zamrud, dan permata yang belum pernah terlihat sebelumnya.

Namun karena tidak ingin bernasib sama dengan Estebanico, de Niza mengurungkan niatnya untuk menakhlukan kota tersebut dan kembali kepada Mendoza. Kisah yang dituturkan oleh de Niza akhirnya tiba di telinga Antonio de Mendoza yang tidak membuang waktu dan segera menyiapkan ekspedisi militer untuk mencari kota yang telah dilihat de Niza, dengan niat untuk mengambil alih tanah-tanah yang kaya itu.

Dalam ekspedisi ini dipimpin oleh Francisco Vázquez de Coronado dengan panduan menurut penuturan Marcos de Niza. Pada 22 April 1540, Coronado meninggalkan kota Culiacan memimpin sekelompok kecil ekspedisi. Akhirnya, Coronado melintasi negara bagian Sonora yang saat ini berada di Meksiko lalu memasuki negara bagian Arizona dan melihat bahwa kisah-kisah de Niza tidaklah benar.

Coronado dan ekspedisinya telah melakukan perjalanan dan pencarian, tetapi tidak pernah menemukan kota emas yang dikatakan oleh de Niza. Ekspedisi Coronado berakhir ketika dia tiba di Hawikuh Pueblo, yang disebut oleh de Niza sebagai tempat dimana Cevola, Tzibola, atau Cibola berada. Setelah tiba di sana, dia menemukan bahwa cerita de Niza adalah kebohongan dan tidak ada harta apa pun di sana, seperti yang dijelaskan oleh de Niza sebelumnya.

Coronado memimpin 350 tentara Spanyol dan 900 diantaranya adalah suku pribumi di utara untuk mencari kota itu. Ekspedisi itu, yang berlangsung sekitar dua tahun, merupakan kegagalan total. Alih-alih menemukan kota-kota besar dengan tembok yang terbuat dari emas, Coronado dan orang-orangnya hanya menemukan desa-desa adat sederhana dengan tembok-tembok lumpur berwarna merah. Akibatnya anak buahnya termasuk Coronado sendiri, nantinya menjadi bangkrut ketika ekspedisi kembali ke Meksiko dengan tangan kosong.

Karena kecewa, Coronado menduduki wilayah itu dengan paksa dan membangun pangkalan yang akan digunakan untuk ekspedisi selanjutnya di masa mendatang. Meskipun Coronado dan anak buahnya gagal dalam pencarian untuk menemukan Kota Emas. Perjalanan mereka membawa mereka melewati wilayah Arizona, New Mexico, Texas dan Kansas, yang kemudian diklaim oleh Coronado sebagai bagian dari kerajaan Spanyol, sehingga mencegah kekuatan Eropa lainnya dari upaya menjajah wilayah barat daya Amerika. Diyakini bahwa Coronado dan ekspedinya merupakan orang pertama yang mengunjungi dan melihat ngarai besar Grand Canyon.