V písomnostiach z 13. – 16. storočia sa obec vyskytuje pod názvom Borolou, Boroszló, od konca 18. storočia aj ako Brestow. Slovenský názov je odvodený od listnatého stromu brest.
Pred r. 1325 bol Brestov majetkom prepošta z Myšle. Pravdepodobne obec získal od Abovcov, ktorí boli v 13. storočí vlastníci okolitých majetkov. Brestov patril prepoštovi nepretržite až do 60-tych rokov 16. storočia. Neskoršie sa stal majetkom šľachtickej rodiny Kataiovcov.
Najstaršia písomná zmienka o obci sa nachádza vo varadínskom registri z r. 1219, v ktorom je zápis, že Biely z Brestova obvinil troch bratov zo Žehne, že mu ukradli rôzne veci v hodnote šiestich hrivien striebra. Aj v ďalšom zápise z r. 1229 sa uvádza spor medzi Petrom, synom Petra a Čepanom, komesom Petrom, Jánom a Pavlom o dedičný majetok. Uvedené zápisy predstavujú najstaršie správy o vlastníctve územného majetku šľachticmi zo Šariša.