Obec Zboj sa spomína v daňovom súpise z roku 1567. Podľa valašského práva bola založená šoltýsom a usadlíkmi okolo roku 1550. Do poslednej štvrtiny17. storočia patrila k humenskému panstvu Drugethovcov.V 18. storočí bola majetkom Csákyovcov, v 19. storočí majetkom rodiny Schmideggovcov. Na rozhraní 19. a 20. storočia tu mala majetky rodina Lobkovitzovcov. V roku 1715 mala obec 28 opustených a 9 obývaných domácností.V roku 1720 pracoval v obci mlyn. O polstoročie neskôr tu už boli dva mlyny, v ktorých hospodárili Leco Čopák a Jacko Čopák. Vlnu chodili Zbojčania, spolu s Novosedličanmi, spracovávať do valchy v neďalekej Starej Stužici (od roku 1945 za štátnou hranicou).
V roku 1787 tu bolo 71 domov, v roku 1828 už 88 domov. Obyvatelia sa zaoberali poľnohospodárstvom a chovom dobytka, príležitostne pracovali v lesoch. Začiatkom 20. storočia pracovala v obci píla. Ďalším zdrojom obživy bola úzkokoľajka na trase Zboj – Nová Sedlica, postavená v roku 1901. V roku 1930 sa začalo s budovaním prípojky do lokality Bystrá.
Počas 1. svetovej vojny, keď sa tu front zastavil zhruba na päť týždňov, bola obec takmer zničená. Počas existencie 1. ČSR, vzhľadom na ťažké životné podmienky, sa veľa obyvateľov vysťahovalo do zámoria za prácou.
V rokoch 1939-1944 bola obec pripojená k Maďarsku. Počas mobilizácie v roku 1941 bolo 80 chlapov z dediny odvedených do maďarskej armády a v roku 1944 zažila obec deportáciu miestnych Židov.Po veľmi ťažkých bojoch bol 18. októbra 1944 Zboj oslobodený. Obec však bola veľmi zničená a spolu s chotárom úplne zamínovaná. Na mínových poliach zahynulo 21 ľudí a 22 sa ťažko zranilo.
Po 2.svetovej vojne sa 69 obyvateľov obce vysťahovalo za prácou do Čiech. V roku 1945 bola v obci zriadená lesná správa. Prvá autobusová linka do obce na trase Snina – Ulič – Zboj bola otvorená 17. júla 1947. V roku 1955 bol v obci zriadený poštový úrad. V roku 1960 bola dokončená elektrifikácia obce. Nový murovaný kostol dokončili v roku 1966. Od roku 1973 hospodáril na tunajšej pôde LPM, š.p., Ulič.
