Le dieu marin Proteus n'apparait guère, et de façon épisodique, que dans une légende, celle du Retour de Ménélas. Cet épisode se trouve déjà chez Homère. Retenus par des vents contraires dans l'île de Pharos, Ménélas et ses compagnons s'allaient périr de famine, quand vint à leur secours Eidothéa, fille de Proteus. Elle apprend au héros que dans l'île habite Proteus, le «Vieux de la mer», devin infaillible, mais qui ne révèle la destinée qu'à qui sait le surprendre et le capturer. Toutes les formes qui se voient sur la terre, lion, dragon, panthère, sanglier, arbre, eau, feu, il les prend successivement. Mais, chaque, jour, à l'heure de midi, il sort des flots, et va se reposer dans une vaste grotte, entouré de son troupeau de phoques. C'est le moment où on peut le saisir. Telle est la plus ancienne version du mythe.
Mais la science grecque a, de très bonne heure, ramené le dieu Proteus aux proportions d'un roi héroïsé. Pour Hérodote, qui prétend reproduire le récit des prêtres égyptiens, Proteus était un ancien roi d'Égypte, héritier de Phéron et prédécesseur de Rhampsinit, qui régnait au temps de la guerre de Troie. Pâris, le ravisseur d'Hélène, ayant été forcé de relâcher dans le pays de Proteus, celui-ci, indigné de la perfidie du Troyen, lui enleva sa captive et ses trésors, qu'il garda jusqu'à ce que Ménélas vînt les lui redemander. C'est à peu près la même version qu'adopte Euripide dans son Hélène : selon ce poète, Pâris n'aurait emmené à Troie qu'un vain fantôme, tandis que la véritable Hélène était, par la volonté de Zeus, transportée dans le palais du roi d'Égypte, Proteus, le plus sage des mortels, pour y vivre pure en attendant d'être rendue à son époux. Enfin, Diodore de Sicile ne se contente pas d'identifier le Proteus des Grecs avec le roi égyptien Célès, qui vivait à l'époque de la guerre de Troie ; il essaie encore d'expliquer le prodige de ses transformations par l'habitude qu'avaient les souverains d'Égypte, dans les cérémonies, de placer sur leur tête des munies de lion, de taureau, de dragon, ou même des arbustes, du feu, des parfums odorants, toutes choses dont la vue frappait le vulgaire de vénération et de terreur superstitieuses.
Les mythologues modernes ont vu, pour la plupart, dans Proteus un symbole anthropomorphique de la mer. Cependant l'érudition contemporaine semble revenir à la conception historique du personnage de Proteus. Pour M. Victor Bérard, Proteus serait le Prouiti ou Prouti des Égyptiens, en d'autres termes le Pharaon qui revient si souvent dans les Contes populaires de l'ancienne Égypte, recueillis par M. G. Maspero, et la légende de Proteus serait un conte égyptien mêlé d'éléments phéniciens. Un fait plus certain, c'est l'influence et la pénétration réciproques des légendes de Néreus, de Proteus et de Glaucos. Ces trois divinités portent l'appellation commune d'alios gerôn, «le Vieux de la mer». Toutes les trois ont en partage la science fatidique et le don des transformations. Toutes les trois, enfin, jouent dans une légende héroïque, Néreus dans la légende d'Héraclès, Glaucos dans celle des Argonautes, Proteus dans celle de Ménélas, le même rôle de divinités prophétiques et auxiliatrices.
O. Navarre