返回古巴——在被封为女王花园的群岛中航行（1494）
在布恩廷波湾起航后，船队再次将航线转向古巴岛，并于5月18日到达了一个巨大的海角，哥伦布将其命名为卡沃-德拉克鲁兹，这个名字沿袭至今。哥伦布在一个较大的村庄登陆，在此受到酋长及其子民的友好款待，他早就听说了哥伦布及其船队。事实上，根据该酋长的报告，哥伦布发现，那些在他第一次航海沿着该岛北部海岸航行期间上船拜访过的无数印第安人，将他们的故事到处传播，他们被视为从天国降临的神奇探访者，关于他们的谣言和惊奇传遍了整个岛屿。舰队司令试图通过该酋长及其人民确定，古巴究竟是一个岛屿还是大陆。他们全都回答这是一个岛屿，但是其疆界无边无际，因为他们宣称，没有人见过该岛的尽头。这个答复，一方面显示了他们对大陆的本质一无所知，同时也让哥伦布的问题依然处于疑惑和不确定之中。古巴省的印第安名字是马卡卡。
重新起航西行的第二天，哥伦布来到一个地方，那里的海岸突然转向东北方向并延伸许多里格，然后再弯曲折回西部，形成一个巨大的海湾，或者说深水湾。他在这里遭到了暴风雨的猛烈袭击，而且还伴随着可怕的雷电，这些纬度上的雷电看起来好似将天空撕裂了一般。幸运的是，风暴持续的时间不长，否则他的处境将危险至极，因为他发现了无数低矮的暗礁和沙滩，这让航行变得很艰难。这种情况随着前行越发严重，后来桅杆顶上的水手举目之处，大海上完全是星罗棋布的小岛：有些小岛低矮裸露、遍地沙子，有的覆盖着碧绿的植物，有的树木参天、森林美丽。这些岛屿大小不一，其长宽从1里格至4里格不等，而且，距离古巴越近，其土壤越是肥沃、海拔越高。发现岛屿的数量在不断增加，根本不可能一一命名，舰队司令便给这个由岛屿构成的迷宫整体命名为“女王的花园”，因为这些岛屿层次变化丰富的绿色恰似给海面镀上了一层碧绿的珐琅彩釉。他最初的打算是从右边离开这个群岛，然后向海洋深处航行，但是他突然想起约翰·曼德维尔爵士和马可·波罗曾经曾提到，亚洲的海岸密布着数千个岛屿。他相信自己现在正置身于其中，并决定不能舍弃看见大陆的机会。如果它果真是亚洲，只要沿着这个航向，他必定很快就能抵达大可汗的疆土。
然而，进入这些岛屿之后，哥伦布很快就被困在最令人困惑的航程之中，他的船队不断面临沙洲、逆流和暗礁的危险与困难。船队被迫以一种摸索的方式航行，桅杆顶上一直有人驻守，随时都用水砣探测深度。有时，他们不得不在一小时内，按照指南针上所有定点改变航向；有时，他们只能在狭窄的海峡窘迫地踯躅而行，那时他们就必须降低所有船帆，把船只拖出来，免得搁浅。尽管采取了所有防范措施，他们还是经常触击沙滩，颇为费劲才能脱困。多变的天气也让他们的航行更加艰难，不久，天气开始呈现出反复无常的任性模式。早晨，海风随着太阳从东方的升起，以此方向吹刮一整天，随着夕阳西下，风也渐渐消失在西方。厚重的云层随着夜晚的来临聚集起来，空中电光闪闪，远处雷鸣阵阵，暴风雨来势汹汹。但是随着皓月升空，乌云四散，有的化作一场阵雨，有的则被兴起于陆地的微风吹散。
周围景物的许多特征都有利于哥伦布的想法，即他现在正置身于亚洲群岛。玻璃般光滑的水道将这些青翠的岛屿间隔开来，船队沿着这些水道滑行，岛上植被瑰丽壮观，淡雅柔和的花香飘荡，花团锦簇，芳香四溢的灌木丛，草地上众多的朱鹤或者更确切地说是火烈鸟羽毛璀璨亮丽，小树林里其他热带鸟类振翅鼓翼，种种迹象均与描述中的东方风土相似。这些岛屿普遍无人居住。然而，他们在最大的岛屿之一发现了一个相当大的村庄，并于5月22日登上了该岛。房屋主人遗弃了自己的居所，看起来他们主要依赖大海维持生计。在这些住所里发现了大量的鱼，邻近的岸边布满了龟壳。另外还有家养的鹦鹉、朱鹤，以及若干哑巴狗，后来才发现，这些狗是专门养肥用作食材。舰队司令给该岛起名为圣玛尔塔。
穿行在这些岛屿之间的时候，有一天，哥伦布看见许多当地人乘着独木舟在其中一条水道平静的水面上忙着捕鱼，不由被他们奇特的捕鱼方式所吸引。他们有一种小鱼，小鱼那扁平的头上附着许多吸嘴，这些吸嘴的吸附力非常强大，一旦粘上任何物体，哪怕被撕成碎片也不会脱落。印第安人在这种鱼的尾部绑上很长的线，将它放入水中，任其自由游走。这种鱼一般都保持在水面附近，直到它感觉到猎物的时候才飞快下沉，将自己的吸嘴贴上鱼的喉咙或乌龟壳下，怎么也不松开。最后，两者都被渔夫拉上来并从水中捞出。就这样，西班牙人见证了一只体形庞大的乌龟被捕获的过程。费尔南多·哥伦布确认，他本人在贝拉瓜海岸还看见以同样的方式捕获鲨鱼。此事已经得到各种各样航海家叙述的证实。据说，在非洲东海岸的莫桑比克和马达加斯加，当地人也采用同样的方式捕鱼。据观察：“虽然野蛮人之间，有可能从未有过相互交流，但是他们在操纵控制动物的模式上却表现出了惊人的雷同。”这些渔民以一种大无畏的姿态登上西班牙人的船。他们向西班牙人供应了鱼，而且很乐意把他们拥有的一切都拿出来。对于舰队司令关于这些地区的询问，他们回答说南部和西部都布满了岛屿，至于古巴，一直向西延伸，没有尽头。
从该群岛脱身之后，哥伦布掉头朝着距此大约14里格的古巴岛山区出发，并于6月3日在一个大村庄上岸。他在此受到了古巴居民那出名的善良和友好的款待，他对此地居民极尽赞美，认为他们的性格比其他所有岛民都温顺平和。他说，他们的动物也比其他岛屿的动物驯服，而且更大更好。当地人欢欢喜喜、十分乐意地从不同地方给他们带来了各种各样的食物，其中野鸽子的个头和滋味尤其不凡。感觉到此鸽子有某种奇特的味道，哥伦布下令把几只刚刚捕杀的野鸽剖开，果然在其中发现了甜香料。
趁着船员们去取水和采购食物的时候，哥伦布便从可敬的酋长和村里的几个长老那里收集信息。他们告诉他，这个省的名字是沃诺非，往西边更远的大海仍然布满了无数岛屿，那里的海水都不深。至于古巴，他们中未曾有人听说在西边有个尽头，即使走上40个月都不能抵达其尽头，事实上，他们认为该岛无边无际。但是，他们提到，舰队司令可以从邻省曼贡的居民那里获得更多的信息，那个省就在西面。这个名字的发音让哥伦布立刻灵机一动，因为曼贡听起来与曼吉类似，曼吉可是大可汗最富饶的省份，那里就靠近海边。他进一步询问了关于曼贡地区的情况，并将印第安人的意思理解为，居住在那里的人像动物一样长着尾巴，他们穿着长袍将其遮掩起来。他回忆起约翰·曼德维尔先生关于东方一些偏远地区的叙述，里面叙述了亚洲某些裸体部落，其中就记录了一个与现在的情况相同的故事，他们在讲述时嘲笑自己文明邻居的衣服，调侃他们衣服的用途仅为了掩饰一些身体缺陷。据此，他变得比以往任何时候都更加自信，认为只要沿着海岸西进，自己最终必定会到达亚洲的文明区域。他自以为是地希望找到的这个曼贡地区就是富裕的曼吉省，其长着尾巴、穿着长袍的人民就是鞑靼帝国的居民。
