코로나도가 이끈 탐험대는 340명의 스페인 군인들과 300여명의 인디언들, 1,000여필의 말, 그리고 1,000여명의 노예들과 6문의 대포로 무장한 주력부대와 에르난도 데 알라르콘(Hernando de Alarcon)이 지휘하는 두 척의 배로 이뤄진 보급부대로 구성됐다.
보급부대는 1540년 8월26일 콜로라도강의 입구를 찾기 위해 캘리포니아만을 거슬러 항해했고, 이보다 앞서 2월 코로나도가 지휘하던 육로 탐험대의 주력부대는 쿨리아칸(Culiacan)을 출발하여 멕시코 서해안 지역을 탐험하면서 북쪽으로 향했다.
그곳에서 소규모로 분리된 한 탐험대가 가이드인 마르코스 데 니사(Marcos de Niza)를 따라서 다시 북쪽으로 이동하던 중 1540년 7월7일, 지금의 뉴멕시코주에서 당시 즈니아족이 사는 전설 속의 시볼라의 일곱 개의 황금도시(El Dorado de Siete Cibola)를 발견할 수가 있었다.

당시 즈니아족은 높은 언덕 위에 4, 5층의 누런 흙벽돌로 쌓은 건물들을 짓고 그 속에서 살았는데, 1,000여개의 방을 가진 큰 집도 있었다고 한다.
태양에 반사된 이 누런 흙벽돌집들은 마치 황금으로 쌓은 집처럼 휘황찬란하게 빛났던 것인데 이를 발견한 코로나도 부대는 많은 희생을 치른 끝에 마침내 도시를 점령할 수가 있었다. 코로나도 자신도 이 전투에서 부상을 당했다고 한다.

그러나 점령한 도시 안에는 황금은커녕 누런 흙벽돌만 나뒹굴 뿐이었다(이 지역은 오늘날 뉴멕시코주 Zuni-Cibola Complex라는 이름으로 1974년 이후 미국 역사 보존지역으로 지정되어 있다).
한편, 코로나도 탐험대의 일부를 이끌었던 가르시아 로페스 데 카르데나스(Garcia Lopez De Cardenas)는 유럽인으로서는 최초로 현재의 애리조나 지역인 콜로라도강의 그랜드캐년(원래의 이름은 스패니시로 Gran Canon(그란카뇬; 어마어마하게 큰 골짜기)이었으나, 후에 영어발음으로 바뀌었다.

탐험대들은 겨울을 지내기 위해 현재의 샌타페(Santa Fe: ‘성 신앙’이라는 뜻의 스패니시) 근처에 있는 리오그란데(Rio Grande; ‘커다란 강’이라는 뜻)에 다시 집결하였다.
당시에는 수많은 유럽의 젊은이들이 일확천금의 꿈을 안고 엘도라도(황금의 도시)를 찾아 신대륙에 발을 들여놓았던 시절이었으며, 또한 수많은 전설과 신화 그리고 탐험가들의 허풍스런 미담에 의해 키워진 황당무계한 이야기들이 끊이지 않았던 시절이었다.

포로로 잡은 한 인디언에 의해 끼비라(Quivira)라고 불리는 북쪽지역의 또 다른 엘도라도 왕국의 존재설이 제보되었다. 희망을 잃어가고 있던 코로나도에게는 귀가 솔깃한 제보였다.
1541년 4월23일, 코로나도는 지금의 캔사스 지역인 끼비라라는 엘도라도를 찾아 이어진 두 번째 탐험에 도전장을 내밀었다.