Карандашные наброски и эскизы к картине появились в начале 1870-х годов. В 1877 году Васнецов с брата Аркадия пишет этюд «Воин в шлеме с кольчужкой». Сюжет картины возник под впечатлением былины «Илья Муромец и разбойники».
В 1877 году была закончена работа над первым вариантом картины. Васнецов выставляет её на VI Передвижной выставке 1878 года.
Окончательный вариант картины был написан в 1882 году для Саввы Ивановича Мамонтова.
Надпись на камне соответствует былинным текстам, но видна не полностью. В письме к Владимиру Стасову Васнецов пишет:
На камне написано: «Как пряму ехати — живу не бывати — нет пути ни прохожему, ни проезжему, ни пролетному». Следуемые далее надписи: «направу ехати — женату быти; налеву ехати — богату быти» — на камне не видны, я их спрятал под мох и стер частью. Надписи эти отысканы мною в публичной библиотеке при Вашем любезном содействии.
Критик Стасов похвалил картину.
В начальных эскизах витязь был повёрнут лицом к зрителю. В последней версии был увеличен размер холста, уплощена композиция, стала монументальней фигура витязя. В начальных версиях картины была дорога, но Васнецов убрал её в версии 1882 года для большей эмоциональности, чтобы не было другого выхода, кроме указанного на камне.
К былинной теме Васнецов также обращался в ранней акварели «Богатырь» (1870) и более поздних картинах «Богатыри» (1898) и «Богатырский скок» (1914)
Картины написаны маслом на холсте. Версия 1882 года хранится в Государственном Русском музее. Версия 1878 года хранится в Серпуховском историко-художественном музее.
Сюжет «Витязя на распутье» воспроизведён на надгробии художника на Введенском кладбище.
