《洞窟物语》的故事发生在一座漂浮在空中的岛上，岛上的原住民是一种好似兔子的类人生物——咪咪卡。咪咪卡是一种和平友善的生物，但若吃下岛上特有的“赤之花”之后，就会变得凶猛狂暴。另外，岛上还有一件蕴藏巨大魔力的宝物——恶魔王冠。为了得到这件宝物，人们派出了一支杀手机器人军队来到这一岛上，而在搜寻宝物的过程中，大部分来自地面的机器人士兵无差别地屠戮咪咪卡。在游戏故事开始前不久，布斯特博士、坂本一家、伊藤与“博士”（本名伊达东彦）组成了科学考察团，来到这座岛上进行研究，但最后却陷入了孤立无援的境地。
故事

玩家角色库特在一个洞窟内醒来，觉察到自己对如何来到此处一事一无所知。走出洞窟后，他发现自己身处咪咪卡的村落之中，而这个村落深受博士之害。其时博士的手下米莎莉和巴鲁罗格正在追捕一个名叫坂本数的女孩，而由于数已被转化为咪咪卡，博士的手下们不仅没有抓到数，还因误认而错绑架了另一只咪咪卡——多隆子。

在此之后，库特在蛋之回廊找到了数，当时她在那儿找到了飞龙之蛋（蛋00），若其孵出飞龙则她可借之逃出这个浮空岛。在从蛋之回廊脱险而归后，数打算要救出她的哥哥数马。但咪咪卡村落的领袖金却抓住了数，要她为多隆子被绑架一事负责；为了多隆子的安全，金甚至打算用她向博士换回多隆子。无奈之下，失去自由的数向库特求助，让库特替她从草丛区救出她的哥哥。

在库特救出数马后，布斯特博士突然出现，并告诉他们博士打算在咪咪卡身上使用赤之花，以组建一支军队，进而征服地面世界。为阻止这一计划，布斯特博士将库特送到砂区，请他抢在博士前头找到赤之花并毁灭掉。库特在砂区遇到了同样失去记忆的女性机器人卡莉·芙蕾斯，以及米莎莉的母亲——保管着赤之花种子的老迈女巫珍卡。珍卡将库特称作“来自地面的士兵”，并将之视为来岛上屠戮咪咪卡的杀手机器人军队的一员。由于巴鲁罗格得到了赤之花存储仓库的钥匙，博士得以获取赤之花，并以多隆子做试验品，强迫她吃下一朵以观其效。这时金出现了，并试图阻止博士，但他尚未碰到博士就被杀害了；而匆匆赶到的库特无力回天，只得眼睁睁看着博士带着赤之花逃走，而自己则被迫杀死狂暴化的多隆子。

为了惩罚妨碍博士的库特，米莎莉将库特传送到了浮空岛深处的一个迷宫中。在探索迷宫时，库特发现卡莉也身陷迷宫，于是他们便携手谋求逃出迷宫。而在途中，巴鲁罗格展现出了它热心的一面，帮助他们移开了堵住迷宫出口的巨石。寻找出路的库特一行遇到了浮空岛的核心，这一核心是种魔力生物，为浮空岛供给维持漂浮状态所需的能量。于是库特一行打败了核心，但博士却立即出现，在浮空岛的漂浮状态被破坏前就转移了核心。之后洪水就会把室内灌满，而为了拯救溺水的库特，卡莉把自己的氧气瓶拆下，接到了失去意识的库特身上。当库特醒来后，若满足一定条件，玩家就可选择拯救卡莉。

回到咪咪卡村落后，库特发现博士已经抓走了所有的咪咪卡；于是库特前去蛋之回廊，并与数马重逢。数马正打算乘飞龙离开浮空岛，并会让库特选择是否与他同行，如果玩家同意，则游戏到此为止——博士征服了地面世界，而库特和数马隐居山中。玩家也可以选择继续对抗博士，并致力于摧毁浮空岛的核心，如此咪咪卡们也能恢复正常。

接着库特从外壁一路向上攀爬，直至到达目的地——大农场，博士便在此处奴役咪咪卡为他种植赤之花。博士的手下抓住了库特，并将晕厥的他关进数所在的牢房内，而后在库特苏醒前带走了数。库特阅读了数离开前留下的信，知道了一切的经过：博士为了得到恶魔王冠，加入了坂本一家和布斯特博士所在的科考队，并在遂愿后立即背叛了他们。在信的最后，考虑到妈妈似乎已有对抗博士的计划，数拜托库特去找她的妈妈。如果早先救出了卡莉，玩家就可以找到一样物品，以恢复卡莉的记忆。卡莉恢复记忆后，想起了以前的事情：玩家角色的真名叫库特，且和卡莉都非当初屠戮咪咪卡的杀手机器人军队的一员；他们来到这个岛上的真正目的是摧毁恶魔王冠，以防其巨大魔力为恶人所利用。库特找到了数的母亲坂本美玲，了解到她正研究如何到达博士所在的岛屿之顶，并正为之制造火箭。在帮她完成火箭后，库特乘上火箭到达岛屿顶部，并穿越最后的洞穴，去对抗米莎莉和博士。此时博士已经提纯了赤之花的精华，并将之浓缩于一块晶体之中，而后借之在库特摧毁其肉体后，使他的精神仍然存活，并占据了浮空岛的核心，与之合为一体，但最后仍被库特摧毁。
核心毁灭后，失去其魔力支撑的岛屿开始坠向地面。这时若满足一定条件，玩家就可进入奖励关卡——关押着恶魔王冠的制造者波罗斯的“圣域”。波罗斯是珍卡的弟弟，曾是一名强大的法师，但在被拷打之后陷入疯狂之中。米莎莉强迫波罗斯制造了恶魔王冠，但她和巴鲁罗格也因此受到诅咒，只得为王冠的持有者效劳。在卡莉的帮助下，库特战胜了波罗斯，从此消灭了使岛屿下坠的负面力量的根源，拯救了岛上的居民；然而，波罗斯所在的封印之间却逐渐崩溃。恰在此时，巴鲁罗格突然出现，将孤立无援的库特两人解救出来。据它自述，米莎莉派它来救援库特一行，以报答他们为她解除诅咒的恩德。最后，库特、卡莉和巴鲁罗格一同离开了浮空岛，并平静地生活下去。