Der Ursprung des Barsois ist bis heute noch umstritten. Manche Ahnenforscher meinen dass er von den altägyptischen Windhunden abstammt, die nach Asien und Europa gelangten. Andere meinen, das seine Vorfahren vermutlich die im mittleren Osten beheimateten „Gaze Hounds“ waren, die sich bei der Jagd ganz auf ihren Geruchssinn verließen. Als sich diese Rasse immer mehr gen Norden ausbreitete, kreuzte man diese Hunde mit einer langbeinigen russischen Collieart. So konnte man ihr die für das Klima notwendige lange Fell und die erforderliche Härte anzüchten. Der Barsoi ist jedoch seit rund neun Jahrhunderten Bestanteil der russischen Kultur und nationaler Geschichte. So findet man in einer französischen Chronik aus dem 11.Jahrhundert den Hinweis, das Anna Iaroslavna, die Tochter des Großherzogs von Kiew, drei Barsois mit sich führte, als sie nach Frankreich reiste, um ihre Hochzeit mit Heinrich I zu feiern. Der Barsoi wurde für die Jagd gezüchtet, wo man bereits im 13.Jahrhundert mit ihm vom Pferd aus Hasen, Füchse, Wildschweine und sogar Wölfe jagte. Viele Zaren und Großfürsten züchteten diese edle Rasse und viele bekannte Persönlichkeiten der russischen Aristrokatie schmückten sich mit diesem Hund, darunter auch Iwan der Schreckliche, Peter der Große, Nikolaus II, Puschkin oder Turgenjew.  Viele bekannte Zwinger züchteten Barsoi, die bekanntesten waren u.a. die des Zaren in Gatschina bei St. Petersburg und des Großfürsten Nikolai Nikolaijewitsch in Perchino.
Bis etwa 1850 gab es keinen einheitlichen Typ; für den heutigen Barsoi selektierten Züchter aus etwa 10 unterschiedlichen Schlägen. Schon im 14. und 15. Jahrhundert wurde der Barsoi in Russland von Großgrundbesitzern zur Hetzjagd benutzt. Bis um 1914 war der Barsoi der „Nationalhund“ der Russen. Etwa Mitte des 19. Jh. begannen die Engländer, die Rasse ihren Vorstellungen anzupassen. Gegen Ende des selbigen Jahrhunderts kam er auch nach Deutschland.