В конце 1539 и в начале 1540 года небольшими отрядами экспедиция выходила из Мехико в Компостелу, где они постепенно собирались для объединенного выступления далее на север. Когда несколько позднее собранное войско покидало Кулиакан, в нем было около 250 всадников и несколько сот пехотинцев с обозом свыше 1000 лошадей и мулов, которые везли все необходимое для длительной экспедиции, насчитывавшей 3–4 тысячи человек. В их число входила группа священников во главе с отцом Маркосом, которым поручалось обращать местное население в католическую веру.
К этому времени путь на север к далекому Кулиакану был уже довольно хорошо обозначен усилиями Гусмана, Кабесы де Вака, Маркоса и Диаса, но некоторые его участки по несколько сотен миль джунглей и гор были далеко не простыми и иногда проходили по землям враждебно настроенных индейцев. В одной из схваток с ними на реке Чиаметла в поселении того же названия был убит его основатель, бывший там вместе с Гусманом несколько лет назад, заместитель Коронадо Саманьега, которого заменил Карденас. Гибель этого способного и смелого офицера произвела тяжелое впечатление на все войско и напомнила всем его участникам об опасностях, которые могли поджидать каждого из них в пути.
Настроение членов отряда вскоре испортилось еще больше, когда там же, в Чиаметле, они встретились с измотанной трудными переходами группой Мельчиора Диаса, которая возвращалась после разведывательной экспедиции по проверке достоверности рассказов отца Маркоса Диас дошел по поручению Мендосы до индейского поселения Чичитликале перед началом большой пустынной полосы, которую он не стал переходить из-за очень сильных зимних холодов и снега, проделав туда и обратно 1500 миль. Хотя его доклад держался пока в секрете, участники этого похода все-таки передали встретившимся путешественникам, что ничего примечательного они нигде по следу Маркоса не обнаружили. Однако сам виновник всей этой экспедиции отбросил такие сообщения как недостоверные и заверил своих уже разочарованных спутников, что у них не хватит рук, чтобы собрать все ожидавшее их впереди богатство.
После встречи с Диасом Коронадо продолжил путь до Кулиакана, где, пользуясь обилием провианта и гостеприимством горожан, он провел несколько дней для отдыха и пополнения провианта. Зная от Диаса, что впереди его ждет долгий и трудный путь через малонаселенные местности с бедными жителями без возможности получения от них продуктов, губернатор решил, что ему лучше пойти дальше с небольшим передовым отрядом, чтобы быстро дойти до Си- болы, тем более, что сообщения Маркоса о ее богатстве были серьезно подорваны главой разведывательной группы.
Он отобрал около 80 всадников и 30 пехотинцев и в сопровождении большого числа индейцев вместе со всеми монахами двинулся дальше на север с запасами рациона на 80 дней. По его плану, основное войско во главе с Арельяно должно было последовать за ним 20 дней спустя, а запасы продовольствия в порт Кулиакана должны были быть доставлены с юга кораблями под командованием капитана Аларкона. Обо всем этом и о ходе экспедиции Коронадо подробно написал Мендосе перед выходом из Кулиакана. Гонцы с рапортом Диаса Мендосе немедленно отправились в долгий путь. Прочитав рапорт, вице-король не мог не испытать разочарование, и, проявляя осторожность, тут же отправил измотанных гонцов обратно на север с инструкциями для Коронадо — идти в Сиболу с небольшим отрядом, оставив основное войско в Кулиакане. План Мендосы удачно совпал с действиями Коронадо, который ко времени доставки инструкций адресату был уже целую неделю в пути со своим авангардом Аларкон с провиантом для Коронадо был направлен морем с поручением взаимодействовать с ним в поисках богатых земель, которые могли лежать дальше на севере по руслу большой реки в конце Калифорнийского залива (море Кортеса), устье которой был открыто Ульоа несколько раньше.
Следуя указаниям вице-короля, Коронадо строго следил за тем, чтобы его люди не отбирали самочинно продовольствие и вещи у индейцев, проявляя к ним уважение, что содействовало бы благоприятному отношению местных жителей к испанцам. Приказы Мендосы предусматривали также, чтобы глава экспедиции вступал в официальное владение всеми землями, открытыми им и его подчиненными. Коронадо проявлял в этом деле большое усердие, проводя соответствующую церемонию даже в тех местах, которые были уже открыты от имени короля Гусманом, Кортесом и отцом Маркосом, видимо, считая, что повтор такого ритуала не повредит.
Несмотря на скептическую реакцию Мендосы после прочтения доклада Диаса в отношении богатств долины реки Майо, Коронадо решил послать туда этого разведчика с группой из 15 всадников для выяснения реального положения. После пяти дней марша-броска Диас вернулся с разочаровывающим сообщением: земля там была действительно плодородная, но жили на ней бедные индейцы-скотоводы, а каких-либо следов обещанного Маркосом золота обнаружено не было. Губернатор направил соответствующее письмо Мендосе, а его отряд испытал еще одно беспокойство, но опять отец Маркое пытался смягчить недовольство людей утверждениями, что главной целью экспедиции должны быть Семь богатых городов Сиболы, а не долина реки Майо.
Марш на север продолжался, но с выходом отряда в долину Майо трудности пути через скалистые и опасные перевалы настолько возросли с потерей лошадей и скота, не говоря уже об изматывании людей и нехватке провианта, что возмущение ложью Маркоса стало всеобщим и громким. Ведь он обещал прекрасную дорогу и богатую долину, а на деле была узкая горная тропа, по которой было опасно пробираться не только животным, но и людям. Когда усталый отряд добрался до поселения Корасонес, он уже потерял несколько негров и индейцев из обоза сопровождения, а также дюжину лошадей. Отрезок пути от Кулиакана до этого места занял около пяти недель, но после четырех дней столь желанного отдыха и сбора продуктов в соседних поселениях Коронадо повел отряд дальше и примерно через 10 лиг вышел в теплую и плодородную долину реки Сонора, откуда он направился к поселению Чичилтикале около начала большой пустынной полосы, где Диас в предшествующую зиму попал в снега и холода.
В этом месте нехватка продуктов стала ощущаться еще более остро, и беспокойство Коронадо в связи с отсутствием ожидаемого провианта с побережья, которое должен был доставить Аларкон, приобрело более серьезный характер. По прямой линии до берега моря было около 200 миль, но к нему с того места вели извилистые и нелегкие тропы. Путевые сведения Маркоса, как выяснялось по маршруту, в целом ряде случаев были далеко недостоверными, как и его описания дороги и богатств этих земель. Главе экспедиции пришлось серьезно задуматься над сложившимся положением. Он решает послать вперед новую группу во главе с Карденасом, который должен был каждый день посылать к следовавшему за ним отряду гонцов с сообщениями об условиях пути и земли. Первые дни пути оказались еще более трудными, чем раньше, но когда отряд вышел к форту Апачи (в сегодняшнем штате Аризона), его встретили зеленые луга, приятные пейзажи и плодородные земли. Сибола уже была значительно ближе и манила к себе еще больше. Наступил июль, а со времени выхода из Компостелы прошло уже шесть долгих месяцев.
Отсюда Карденас снова был послан вперед на день пути, так как Коронадо, помня о расправе жителей Сиболы с Эстебаном и его людьми, решил проявить больше осторожности. На второй день разведки перед Карденасом появились четыре индейца из Сиболы и объяснили, что они были посланы приветствовать испанцев и заверить их в благорасположении их города и в готовности снабдить пришельцев продуктами, что страшно обрадовало изголодавшихся путешественников. Карденас отправил двух из этих индейцев обратно с сообщением о скором приходе в Сиболу высокого представителя короля Испании и с просьбой к горожанам спокойно оставаться в своих домах до его прибытия. Два туземца были оставлены в качестве заложников, а Альварадо был послан с рапортом для Коронадо о встрече с людьми из Сиболы.
