Menelaj je od Protejeve kćeri, Idoteje, naučio da bi mogao doznati kojeg je boga uvrijedio i kako bi se mogao iskupiti i vratiti kući, i to kad bi uhvatio njezina oca. Naime, Protej može predvidjeti budućnost, ali odgovaranje na upite izbjegava mijenjanjem oblika, pa predviđa budućnost samo onima koji ga uspiju uhvatiti.
Protej je isplivao iz mora da bi spavao sa svojim tuljanima, ali ga je Menelaj uspio zadržati, bez obzira na to što je Protej preuzimao obličja lava, zmije, leoparda, svinje, a čak i vode i stabla. Protej mu je potom istinito odgovorio, rekavši mu i neke dodatne pojedinosti - da je njegov brat Agamemnon ubijen, da je Ajant mlađi poginuo i da je Odisej zaglavio na Kalipsinu otoku.
Aristejeve pčele
Vergilije u svojim Georgikama govori da su sve Aristejevepčele umrle od neke bolesti. Aristej je otišao svojoj majci Kireni i zamolio je za pomoć, a ona mu je rekla da mu Protej može reći kako da spriječi takvu katastrofu. Aristej je morao uhvatiti Proteja, a to je i uspio, te mu je Protej rekao da žrtvuje dvanaest životinja bogovima, a da trupla ostavi kao žrtvu te da se vrati poslije tri dana. Kad se Aristej vratio, u jednom je truplu našao mnoštvo pčela. Odnio ih je kući, u pčelinjak, a njegove pčele više nikad nisu oboljele.