Nález z doby bronzovej svedčí o tom, že územie súčasnej dediny Vyšný Čaj bolo osídlené už v dobe predhistorickej. V regióne obcí Vyšný čaj - Nižný Čaj sa našiel aj materiál z obdobia ranného stredoveku a to nádoby z piesočnatej hliny. To jasne svedčí o slovanskom sídlisku, ktoré je datované do 9. storočia.
Konkrétne prvú správu o Nižnom Čaji poznáme zo začiatku 14. storočia. V tom čase obec spolu s Vyšným Čajom patrila tej vetve z rodu Aba, ktorej posledným žijúcim členom bol Dominik, syn Lacka, ktorý sa označoval prediktátom z Trsteného pri Hornáde (de Nassad), pretože tam mal svoje sídlo. Dominik, syn Lacka, zomrel ešte pred rokom 1333 bez mužského potomka. Král Karol Róbert daroval jeho majetky palatínovi Viliamovi Drugethovi v roku 1335. Ten v tomto čase už držal hrad Slanec a jeho panstvo. Patrili mu teda dediny Trstené pri Hornáde, Ždana, Skároš, Nižný a Vyšný Čaj, Olšovany , Bohdanovce , Košická Polianka , Trstany a čiastka v Krásnej nad Hornádom . Z území ešte vlastnil zem v susedstve dedín Vyšný a Nižný Čaj v Abaujskej stolici a Šarišské Lužniaky v Šarišskej stolici. Podľa uvedenej prvej písomnej zmienky z roku 1335 teda vieme, že v tom čase už existovali obce Vyšný Čaj aj Nižný Čaj ako vyvinuté dediny.
Nevieme odkedy a za akých okolností získali predkovia Dominika, syna Lacka, do vlastníctva Nižný Čaj. Poznáme však skutočnost, že v roku 1270 pri opise panstva hradu Füzér (ten je už na madarskej strane v blízkosti jazera Izra), patrila zem Skároš, susediaca s panstvom Füzér, Mikulášovi, synovi Abu, ktorý bol starým otcom Dominika, syna Lacka. Vieme aj to, že spomínaný Mikuláš, syn Abu sa v roku 1290 uvádza s prediktátom z Olšovian (de Elswa), kde musel mať svoje sídlo. Je teda viac ako pravdepodobné, že už v tom čase vlastnil aj obce Nižný a Vyšný Čaj, ktoré s Olšovanmi priamo susedia. Historik Branislav Varsik nepochybuje, že obe obce existovali už v 13. storocí. Dominik, syn Lacka, mal však dcéry a žijúcu manželku a tým podla vtedy platných zákonov prináležalo dedičstvo, tzv. dievčenská štvrtina. Vilam Drugeth bol teda v roku 1337 po dlhšom spore nútený vrátiť tri dediny. Takto Klára, dcéra Dominika, získala Olšovany a Klára, vdova po Dominikovi, získala Nižný Čaj. Pani Magic, dcéra Lacka a sestra Dominika, získala Vyšný Čaj.
O osude vyšného Čaja po roku 1337 nevieme nič. Až v roku 1427 sú obe dediny (Vyšný i Nižný Čaj) v rukách vdovy po Šimonovi. Nevieme však, v akom príbuzenskom pomere bola k predošlým držiteľom. Portálny súpis z roku 1553 udáva, že vo Vyšnom Čaji bolo 5 port, čiže usadlostí. Zvyčajne sa zvykne rátať niminálne 5 ľudí na jednu usadlosť, čo svedčí, že v tomto roku Vyšný Čaj obývalo približne 25 obyvateľov. Nebola to teda ľudnatá dedina. V roku 1564 tu bolo 5 a 1/2 porty. Desiatkový súpis z roku 1565 vykazuje, že vo Vyšnom Čaji žilo 10 sedliakov a 3 želiari. Z týchto obyvateľov mali len traja mená slovanského pôvodu, dvaja maďarského a ostatní neistého pôvodu. Desiatkový register z roku 1577 udáva, že tu žilo 13 sedliakov. Traja mali mená slovenského pôvodu, dvaja maďarského, ostatní neistého.
Miešalo sa tu teda obyvateľstvo slovenské, maďarské a snáď i nemecké. Súpis z roku 1598 uvádza, že vo Vyšnom Čaji bolo 12 domov.
V 16. storočí v čase reformácie tu slúžili maďarskí reformovaní kňazi, čo malo ďalší vplyv na vývoj národnostného cítenia obyvateľov dediny. V roku 1577 tu napr. slúžil kalvínsky kňaz Šimon Enizkei. V 17. a 18 storočí tu došlo v dôsledku moru a Rákociovských povstaní k značnému vyľudneniu. V roku 1715 boli vo Vyšnom Čaji len štyria poddaní sedliaci, ale po roku 1720 tu začalo prichádzať nové obyvateľstvo. Konskripcia cirkví a farárov z roku 1746 udáva, že sa tu rozprávalo približne rovnakým dielom slovensky i maďarsky. Podľa vierovyznania tu vtedy žilo 14 rím. katolíkov, 3 gr. katolíci, 5 luteránov, 15 kalvínov a 13 detí. Celkovo teda 50 obyvateľov. V roku 1851 žilo v obci 162 rím. katolíkov, 100 kalvínov a 15 židov. Bola to teda obec prevažne slovenská a mala už 277 obyvateľov. V roku 1930 tu žilo 315 Slovákov, 31 Maďarov a 9 inozemcov, celkovo 354 dedinčanov. Asfaltovou cestou bola dedina s okolím spojená a v roku 1961.
Názov obce pochádza od slovanského mena Čavoj, ktoré bolo neskôr pomaďarčené a novým vývinom spätne poslovenčené, avšak už z maďarského názvu na Čaj. Z rovnakého základu vznikli aj obce Čavoj pri prievidzi a Čejov v Českej republike.