永胜县程海一带，在唐代属南诏国成纪镇，当时程海叫“龙佉河”；宋代，文献记载为“程河”。称湖泽为“河”，是汉晋遗风，如洱海叫“叶榆河”、“洱河”，滇池叫“滇池河”等。明代，“程海”正式出现在文献记载中，沿袭至今。但是，程海湖为什么叫“程海”？至今众说纷纭，没有定论。

关于程海的来历，永胜民间至少流传着5个大同小异的陆地陷落“成海”的版本，这则故事说：很久以前，程海所在地是一块水草丰沛、粮食高产、人烟稠密的平地，人民丰衣足食，过着幸福的生活。有一天，这里来了一位先生（又说菩萨，还说是老者，反正是足智多谋、未卜先知者），警示人们说：灾难就要来了，请注意寺庙前那一对石狮子的眼睛，如果狮眼血红，赶快逃命！于是，人们开始注意石狮的眼睛。可是，左瞧右看，石狮的眼睛怎么也不红，一个顽童淘气，从母亲化妆盒里偷得胭脂，便将狮眼涂红了。立时天旋地转，转瞬间陆地下陷，洪水淹没了一切……

这个故事广泛流传于永胜全境，对诠释“程海的来历”，颇有影响，连一些地方志书都受其左右。然而，仔细分析不难看出，这个故事的产生，明显受明正德六年（1511年）当时北胜州大地震的影响，因而，有两个版本开头干脆就说“明宣德年间，有位老师……”，“传说在五百年前，程海并不是现在的景象”云云。（《中国民间故事全书·云南永胜卷》30-37页，知识产权出版社2010年1月第一版。）可史载正德年间的大地震却是：“城北大树坪旧州城全部倾毁，民房被毁5000余间，人口伤亡千余人，土地冲毁、淹没者1万间；城西北红石岩震塌，三川坝西山草海形成”（《永胜县志》第11页，云南人民出版社1989年3月第一版），并没有说程海形成于此时。因此，明代天启（1621-1627年）《滇志》所言“相传本陆地，有姓程居此，一夕忽沉为海”，也仅仅是“传言”，不足为信。现代科学证明，程海形成于距今160万年前的第四纪，是因喜马拉雅山造山运动而成的地堑湖，成湖已久。

还有一说，程海之名是“有姓程居此”。

现在已无法考查，南诏国在程海周边设“成纪镇”时，与永胜如今还有的古老“成”姓有何关系。这“成”姓，最早可能是生活在程海沿岸的，当时蒙氏在程海东岸山头筑崀峨城，且命名领地为“成纪镇”，实与地理、姓氏有关。程海之“程”，最早可能是“成”。宋代与云南地方多有阻隔，“成”姓极有可能误听误写为“程”（也有作“陈”的），也使“龙佉河”成为“程河”。而云南明代汉人按其称“湖泊”为“海”的习惯，正式改称“程海”，其道理类似大理的“洱海”。

也有人说，程海是永胜境内程、海两大姓氏的合称。此说不无道理。原因是，永胜少数民族中的程、海二姓，确实是当地的旺族，他们最早在程海边居住，明代才渐渐往今华坪县和永胜县良峨、六德等地迁徙。在六德、崀峨，如今程、海二姓仍为大姓。现崀峨一块古碑就曾记载，其祖先正是生活在今程海南岸今清邑一带的。现在，无论是永胜还是华坪的海姓傈僳族（自称“黑咱扒”，他称“黑傈僳”），老人去世，由祭司“尼扒”念诵《指路经》将其灵魂送归祖先居住地时，其中反映的迁徙路线正是丽江-梓里-程海-永北-六德-华坪-东风。而现程海湖畔不少用汉字、汉语无法解释的古地名，用傈僳话一讲，却清楚明白，也可证明程、海二姓跟湖名的关系。