Prvá písomná zmienka o obci je z roku 1345, kedy bola súčasťou panstva Chmeľovec. Ohraničenia majetkov hradného panstva Šebeš v roku 1345 sa z poverenia kráľa Ľudovíta I.zúčastmil aj zeman Mikuláš, syn Dominika z Nadveja. Používanie názvu tejto dediny v prídomku Mikuláša dokazuje nielen vlastníctvo majetku, ale najmä to, že Mikuláš býval v tunajšej fúrií. Z toho je zrejmé, že miestne sídlisko jestvovalo už pred rokom 1345. Zeman Mikuláš s bratmi Jakubom a Vavrincom v roku 1351 použili v pedikáte názov dediny Chmeľovec a ďalej listina uvádza vtedajší názov Chmeľovca a Nadveja v stotožňujúcom spojení. Zo vzájomnej zemepisnej polohy oboch dedín a ich názvov vyplýva, že Nadvej vznikol na pôvodnom majetku Komloš a bol mladším sídliskom ako Komloš. Nadvejskí zemania nepochybne pochádzali z rozvetvených komlošských zemanov, pričom Nadvej vznikol ako zemianska osada, resp. dedina. Na popud zemanov ju vybudovali poddaní z Komloša v druhej polovici 13. alebo začiatkom 14. storočia. V písomnostiach zo 14. – 16. stor. sa vyskytuje pravidelne pod maďarským názvom Nadfó zloženom zo slov: nád = trstina a fó = vyšný, horný. Názov vznikol opisom zemepisnej polohy majetku resp. sídliska ležiaceho v hornej časti údolia tunajšieho potoka. Nemožno pochybovať o tom, že maďarský názov Nadveja vytvorili miestni zemania. Z maďarského názvu vznikol fonetickou úpravou slovenský názov Nadvej.
Zmeny názvu obce
Názov obce sa v priebehu času menil, v roku 1345 bola známa ako Nadfu, v 1351 ako Nadfeu alebo Kolmos. V rokoch 1773 ako Nadwej, v 1786 ako Nadfej. V roku 1927 sa ešte používal názov Nadwej. Od roku 1948 je obec dodnes známa ako Šarišská Trstená.