Именно Кесаде губернатор решил доверить руководство экспедицией. По первоначальному плану ее должен был возглавить сын де Луго Алонсо, но как раз в этот момент, похитив кое-какие из собранных отцом драгоценностей, он бежал в Испанию, предпочтя спокойную и обеспеченную жизнь на родине тяготам и риску поисков Эльдорадо. Кесада же, как понял губернатор, был наделен почти всеми способностями, какие только требовались, - и умением увлечь за собой остальных даром слова, и дальновидностью. Пожалуй, единственное, чего ему не хватало, так того, что он не был профессионалом-военным, но ведь в экспедиции и так немало и солдат, и дворян-воинов.
Сначала надо было выбрать путь в глубь материка. Проще всего было бы подняться вверх по течению Магдалены, но губернатор располагал лишь несколькими небольшими судами. На них решено было отправить только часть отряда. Основным же предстоял пеший путь. Однако дельта Магдалены была болотистой и непроходимой. Значит, надо было обойти этот гиблый край стороной: сначала пройти вдоль морского побережья на восток и только потом, когда кончатся трясины и мелкие озера, повернуть на юг и выйти к среднему течению реки, к назначенному месту встречи с судами, чтобы дальше пойти в места еще совершенно не изученные.
5 апреля 1536 года жители Санта-Марты вышли провожать экспедицию Кесады в поход. Пешие отряды, вооруженные пиками и аркебузами, в боевом порядке выстроились на морском берегу. Весело гарцевали всадники - их было семь десятков. Под тяжестью тюков с провиантом и снаряжением сгибались пленные индейцы - именно им предстояло нести весь груз.
Сначала, как и было намечено, маршрут лежал вдоль побережья Карибского моря. Берег был каменистым, и путь оказался тяжелым. Первые дни похода выдались очень жаркими, испанцы тотчас же начали страдать от жажды. К тому же почти сразу начались нападения индейцев: краснокожие воины появлялись внезапно, осыпая пришельцев градом стрел, и столь же внезапно исчезали. Белые люди; принесшие местным жителям столько зла, не могли рассчитывать здесь на гостеприимство. Но войско упрямо продвигалось вперед. Вскоре оно достигло селения Рамада, откуда ему предстояло повернуть на юг.
Отряд испанцев медленно, с огромным трудом продвигался в глубь неизвестной страны.
Только через четыре недели утомительного пути Кесада дал своим людям и себе самому небольшой отдых. Они остановились в одном из индейских селений; местные жители встретили их мирно. Здесь испанцы пополнили припасы и привели в порядок снаряжение. Затем отряд двинулся дальше. Теперь продвигаться приходилось сквозь дремучие тропические леса, представляющие собой непроходимое переплетение стволов, веток и лиан. Лес был полон хищных зверей, кишел змеями.
Кесада, отобрав наиболее выносливых солдат, вооружил их тяжелыми ножами и топорами; они должны были прорубать дорогу в этой чаще.
В отряде появились больные тропической лихорадкой. Продукты были на исходе. Людям пришлось есть ящериц, змей, летучих мышей. Но 26 июля 1536 года они все-таки вышли на правый берег Магдалены, обогнув, как и было намечено, ее топкую дельту, и стали дожидаться судов, на которых поднималась вверх по течению другая часть отряда.
Однако ждать пришлось долгих два месяца.
Вскоре кончились последние остатки еды, в лагере, разбитом на берегу Магдалены, начался голод. К тому же наступил период тропических дождей - настоящих водопадов.
Когда пришли корабли, выяснилось, что флотилия, которую ждали, попала в страшный шторм. Тогда Педро де Луго снарядил несколько новых судов, но на это потребовалось время...
Отряд Кесады двинулся вверх по реке Магдалене, вступив в совершенно неизвестные европейцам земли.
Через несколько дней матрос с идущей первой бригантины заметил на берегу какое-то индейское селение. Когда испанцы вошли в него, хижины оказались пустыми - заметив корабли, все жители скрылись в лесу. Но на полях вокруг селения в изобилии рос маис, его спелые початки заполняли амбары домов.
Экспедиция провела здесь три зимних месяца. Первое время запасов маиса было довольно, и солдаты быстро восстанавливали силы. Когда маис кончился, в отряде вновь начался голод.
Теперь последствия его были страшными: ежедневно умирали по нескольку человек, войско Кесады таяло буквально на глазах. Тела умерших сбрасывали в Магдалену, и течение уносило их вниз, в сторону Санта-Марты, откуда начался поход.
Кесада послал одну из бригантин вверх по течению Магдалены на разведку. Но три недели спустя судно возвратилось с малоутешительными вестями: впереди, по обеим сторонам реки, был все тот же непроходимый лес.
Тогда Кесада решил изменить маршрут. Продолжение прежнего - вверх по реке - означало бы верную гибель экспедиции. Между тем захваченные испанцами во время редких вылазок индейцы рассказывали о том, что не так уж далеко отсюда, в горах, живет племя, которое умеет добывать соль. Соль для индейских племен всегда была предметом роскоши, она стоила очень дорого. Племя, которое умеет добывать соль, должно быть очень богатым племенем.