В 1485 году Колумб с сыном Диего переезжает в Испанию (возможно, бежит от преследований). Зимой 1485—1486 годов он находит приют в монастыре Санта-Мария-да-Рабида. Настоятель Хуан Перес де Марчена принял его и организовал первое письмо к Эрнандо де Талавере, его знакомому — духовнику королевы, с кратким изложением идей Колумба. Король Испании находился в это время в городе Кордове, где проходила подготовка к войне с Гранадой с личным участием государей. В 1486 году Колумб смог заинтересовать своим проектом герцога Медина-Сели. Поскольку его собственных финансов было недостаточно для организации экспедиции на запад, Медина-Сели свёл Колумба с королевскими финансовыми советниками, купцами и банкирами и со своим дядей — кардиналом Мендосой. Зимой 1486 года Колумб был представлен Педро Гонсалесу де Мендосе, архиепископу Толедо и великому кардиналу Испании, который, в свою очередь, посодействовал аудиенции у католических королей. Для изучения предложений Колумба была назначена комиссия богословов, космографов, юристов, монахов и придворных во главе с Талаверой. Комиссия заседала четыре года, но по причине скрытности Колумба и его нежелания раскрывать планы так и не вынесла окончательного вердикта. 20 апреля 1488 года Колумб, следовавший за королевским двором из города в город, неожиданно получил письмо от португальского короля с предложением вернуться в Португалию: « И если Вы опасаетесь Нашего правосудия по поводу некоторых Ваших обязательств, то знайте, что ни после Вашего прибытия, ни во время пребывания в Португалии, ни после отъезда, Вы не будете ни арестованы, ни задержаны, ни обвинены, ни осуждены, ни преследуемы по какой-либо причине, вытекающей из гражданского, уголовного или какого-либо другого права. » Колумб направляет свои предложения и по другим адресам: от короля Англии Генриха VII в феврале 1488 года он получил благосклонный ответ, но без каких-либо конкретных предложений. В 1491 году в Севилье состоялось повторное личное свидание с Фердинандом и Изабеллой. Результат для Колумба был снова неутешителен: «Ввиду огромных затрат и усилий, необходимых для ведения войны, начало нового предприятия не представляется возможным». К переговорам было решено вернуться после окончания войны. В 1491 году Колумб обращается к герцогу Медина-Сидония, крупнейшему магнату, владельцу около ста торговых кораблей, но и от него получает отказ. Наконец, в январе 1492 года состоялось долгожданное событие — взятие Гранады. Колумб, видимо, сильно переоценил победный энтузиазм короля Испании: когда он сформулировал те условия, на которых он предполагал открывать и владеть новыми землями (назначить его вице-королём новых земель, наградить его титулом «главного адмирала моря-океана»), Его величество признал требования Колумба «чрезмерными и неприемлемыми», переговоры были прерваны, а король отбыл из Санта-Фе. Колумб в феврале 1492 года уезжает в Кордову, а затем декларирует намерение и вовсе эмигрировать во Францию. Здесь шаг навстречу сделала королева Изабелла. Идея грядущего освобождения Гроба Господня настолько захватила её сердце, что она решила не давать этого шанса ни Португалии, ни Франции. Хотя Испанское королевство и было образовано в результате династического брака Фердинанда Арагонского и Изабеллы Кастильской, их монархии сохранили, однако, отдельные самостоятельные администрации, кортесы и финансы. «Я заложу свои драгоценности», — сказала она. 30 апреля 1492 года королевская чета жалует Колумбу и его наследникам титул «дон» (то есть делают его дворянином) и подтверждает, что, в случае удачи заокеанского проекта, он будет Адмиралом Моря-Океана и вице-королём всех земель, которые он откроет или приобретёт, и сможет передать эти титулы по наследству. Тем не менее, деньги на снаряжение экспедиции Колумбу предстояло искать самостоятельно за счёт недополученных государственных налоговых платежей Её Величества королевы Кастилии. К тому же по договору восьмую часть расходов должен был нести сам Колумб, у которого вообще не было ни гроша. Однако Колумбу помог Мартин Алонсо Пинсон. Один из кораблей, — «Пинта» — был его собственный, и снарядил он его за свой счёт; денег на второй корабль он дал Христофору в долг, чтобы Колумб мог сделать свой формальный вклад по договору. На третье судно деньги под его же поручительство выдали местные марраны (крещёные евреи) в зачёт своих платежей в бюджет. Среди них был раввин и королевский казначей Авраам Сениор (Коронель) и его зять Майера Меломед.