在大约距今1万年前的冰河时期台湾是与大陆相连的。来自华北与华南的大量哺乳动物通过陆桥来到台湾，而史前时代的猎人们则追寻着猎物的足迹来到这里。大约在距今五六千年前一群善于航海的人驾着独木舟来到了如今的台湾西海岸并在这里繁衍出独特的大坌坑文化。以大坌坑文化为代表的新石器文化最早出现在台湾面向大陆的西海岸，然后慢慢在全岛范围内扩散开来。多元化的台湾史前文化由此逐渐形成。
如今大坌坑文化被大多数学者认为是台湾原住民的早期祖先。在汉人尚未移居台湾之前岛上的原住民分成一个个互不相属的部落族群。台湾原住民的语言属于南岛语族的一部分。南岛语是世界上唯一主要分布在岛屿上的大语系。澳洲学者贝尔伍德认为南岛语是从台湾扩散到东南亚的，但台湾并不是南岛语的发源地。南岛语族的祖先在距今约5000~6000年前从今天的福建迁徙到了台湾。
位于中国东南沿海的福建省长达三千多公里的海岸线孕育出了新石器时代的海洋族群。与台湾大坌坑文化同时期同类型的新石器时代遗址在福州闽侯昙石山、平潭岛壳丘头等多处发现。2001年地处闽江出海口的马祖亮岛先后发掘出两具“亮岛人”骨骸。这两具骨骸经测定分别为距今8300年和7500年。这两具骨骸的主人被确认与今天的台湾原住民及东南亚的南岛语族有着母系血缘的亲缘关系。
除大坌坑文化之外台湾发现的新石器文化遗迹还有台北圆山文化、营埔文化、台东卑南文化、台北十三行文化......新石器时代的闽台文化同属以“采贝经济”为主的海洋贝丘文化。福清东张遗址发现稻谷遗迹，台湾凤鼻头遗址陶片上有稻米的遗留说明四五千年前的新石器时代晚期闽、台两地先民已开始种植水稻 。 台湾的早期史前文化基本上是中国大陆南部区域文明的派生亚种。从那时起海峡两岸的文明关系就从未间断过。
看似孤悬海上的台湾在早期历史阶段其实并不是处于一种孤立状态。在台湾少数民族的传说中保留着祖先与外来族群在岛上斗争、交流、融合的故事。在台湾少数民族的传说提到最多的一个外来族群是矮黑人。矮黑人作为东南亚的古老人种如今零星分布于菲律宾的吕宋、内格罗斯、巴拉望、棉兰老等和马来半岛的泰马两国边境地区以及印度的安达曼群岛。台湾的少数民族大多都有关于祖先与矮黑人相处的传说。
这些传说中对矮黑人形象的刻画是相似的：矮黑人身长不过三尺，行动敏捷且有高超的生活技能，甚至还精通神秘的巫术。如今生活在新竹一带的赛夏族还保留着传统祭祀仪式“矮灵祭”。在赛夏族的传说中他们的祖先曾与矮黑人友好共处。在这一过程中矮黑人教会了赛夏族种粟、收割、跳舞和巫术。后来因为矮黑人对赛夏族女子的觊觎引发了纠纷战斗。赛夏人用计谋全歼了矮黑人。
相传矮黑人败亡时对赛夏人发下了恶毒的诅咒。从此赛夏人就在每两三年收割粟米后举行矮灵祭：通过祭拜那些遇害的矮黑人以免冤魂骚扰，同时也以这种祭祀以史庆贺丰收。在邵族、邹族、布农族、泰雅族的传说里都活跃着矮黑人短小轻捷的身影。在清代的《凤山县志》等文献中矮黑人的形象呼之欲出。如今台湾、大陆、日本的学者多认为矮黑人来自于菲律宾或是中国大陆的苗族。
闽、台两地考古学者发现的商周时期文化遗址、遗物等证实了远古时期海峡两岸经济文化关系十分密切。商周时期从大陆输入的青铜器具提高了台湾的生产能力。春秋战国时期台湾被称为“岛夷”，到了秦朝改称台湾为“瀛州”。东汉时期的纪传体史书《后汉书》将台湾称为“夷洲”。“夷洲”这一称呼延续到隋唐时期被“流求”取代。“流求”一词有时也写作“琉球”。明朝中期以后民间对台湾的称呼变得多元化。
明朝以前大陆对台湾的记载主要集中于官方典籍之中，而普通人在当时的航海技术条件很难实地造访台湾。明代海峡两岸之间的民间交流开始进入活跃期：当时大陆民间称台湾北部为“鸡笼”，称台湾西海岸为北港，又用“大员”、“台员”等称呼指代全岛。同一时期明朝官方则称台湾为“东番”。一般认为“台湾”这一名称正是明代闽南人所使用的“大员”这一称呼演变而来相清康熙年间台湾府设立后“台湾”这一名称正式成为这座岛屿的官方名称。