Как человек глубоко верующий, Адмирал, много размышлявший над тем, почему по божьему промыслу, как он считал, катастрофа, постигшая «Санта-Марию», произошла именно в этих местах и именно в день Рождества Христова. Он наконец пришел к выводу, что Всевышний хотел тем самым ему сообщить, что он должен именно здесь основать первое испанское поселение и что материал, оставшийся от его погибшего флагмана, должен послужить для строительства такого укрепленного поселения. «Наш Господь, — записывает глава экспедиции в своем дневнике, — сделал так, чтобы корабль сел на мель в этом месте, с целью возведения на нем поселения». К этому его очень настойчиво призывал и сам Гуаканагари, который видел в присутствии на собственной земле могущественных союзников залог своего успеха в постоянной борьбе с многочисленными местными врагами. С учетом всех рассуждений и обстоятельств, в том числе явной перегруженности «Ниньи» двумя экипажами, Колумб отдает распоряжение построить укрепленное поселение под названием «Вилья Навидад», или «Город Рождества», то есть в честь дня, когда произошло столь знаковое событие.
Первое и очень скромное европейское поселение во вновь открытых землях было воздвигнуто очень быстро и в основном на материалах остова адмиральской капитаны. Желающих остаться в новом поселении оказалось больше, чем было нужно, поскольку большинство добровольцев, убедившись в наличии в этих краях золота, рассчитывали здесь немало разбогатеть и впоследствии вернуться со своим богатством в Испанию. Всего в Навидад остался 21 человек во главе с другом Колумба Диего де Арана. Для его укрепления в поселке были построены башня и форт, а вокруг него в соответствии со средневековым обычаем вырыли ров. Адмирал позаботился и о том, чтобы у остающихся в Навидад людей были хлеб и вино на протяжении целого года, чтобы в их распоряжении имелись семена для посева зерновых, чтобы среди них были специалисты различных особенно нужных профессий — плотник, бондарь, кузнец, пушкарь и другие, то есть все то, что могло максимально удовлетворить насущные потребности новоселов далеко от цивилизации на время его отсутствия. Одновременно с этим Адмирал принял решение вернуться в Испанию, чтобы доложить монархам о его успешном открытии Индий и поскорее вернуться в новые земли для продолжения их исследований и нахождения их новых богатств.
27 декабря Гуаканагари и несколько его родственников вновь посетили Колумба и снова вручили ему золотые подарки Вождь индейцев не хотел отъезда Адмирала и стремился задержать его отплытие обещаниями золота, которое должны были через какое-то время по его просьбе доставить из центра страны. Но поскольку решение Колумба поменять было нельзя, он просил его взять с собой одного из своих братьев и одного другого родственника. Адмирал обещал подумать над этой просьбой своего нового друга. Во время этой встречи прибыли индейцы, которые сообщили испанцам, что в устье одной из рек на побережье острова появилась другая каравелла — это была тайно исчезнувшая в поисках золота «Пинта» Мартина Пинсона. Гуаканагари тут же распорядился послать за ней одно из своих быстроходных каноэ. Теперь усиленный экипаж «Ниньи» начал готовиться к отплытию в Испанию, проводя необходимые ремонтные работы на каравелле, а также запасаясь питьевой водой, дровами, продуктами и образцами местной флоры и фауны.
30 декабря в разгар одного из прощальных празднеств один из прибывших индейцев сообщил Колумбу, что два дня назад он сошел с каравеллы «Пинта» к востоку от места проходившей встречи — Мартин Пинсон, видимо, хотел вернуться под крыло Адмирала, что последнего очень обрадовало. Начатый праздник прощания был продолжен. Колумб решил отблагодарить Гуаканагари действительно ценным подарком, передав ему снятые с себя изящное ожерелье, очень красивую нить бус, давно понравившееся индейскому вождю серебряное кольцо и, наконец, великолепную пурпурную плащ-накидку, которые он собственными руками надел на своего друга. Вслед за этим ему были преподнесены также совершенно новые цветные котурны. Гуаканагари пришел в невероятный восторг от таких ярких и нарядных вещей и не остался в долгу. По его сигналу два вождя других местных племен преподнесли Адмиралу две больших пластины из чистого золота. Обе стороны остались очень довольны друг другом.