В обзоре Eurogamer, опубликованном в 2000 году, насыщенный неожиданными поворотами сюжет игры в шутку уподоблен «четырем змеям, играющим в твистер». По словам анонимного автора обзора, за почти невинным фасадом игрового процесса Vagrant Story скрывается глубокая и сложная ролевая система, которая заставит поломать голову даже самого опытного искателя приключений. Особо был отмечен перевод игры и сказано, что переводчики достойны медали за свой труд. В ретрообзоре 2012 года, также опубликованном на портале Eurogamer, обозреватель Саймон Паркин (Simon Parkin) посчитал, что стержнем сюжета игры, скрытым под покровами средневековых интриг, гримуаров и борьбы за власть методами плаща и кинжала является противостояние двух героев, Эшли Райота и Сиднея Лосстарота. Последний назван в обзоре Eurogamer «самым завораживающе жутким» из всех образов злодеев, когда-либо созданных Square. Систему создания и усовершествования оружия Паркин назвал головокружительно гибкой, а общую атмосферу игры — тяжелой и гнетущей, в первую очередь благодаря детально разработанным декорациям. Паркин подчеркнул, что благодаря профессиональной режиссуре и изощренной работе камеры внутриигровые сцены покинули рамки обычной для компьютерных игр пантомимы и стали чем-то большим.

Обозреватель журнала Edge назвал игру «атипичной во всех возможных отношениях»; с его точки зрения, даже обложка Vagrant Story обманчива — изображенные рядом персонажи, Эшли Райот и Калло Мерлоуз, в игре практически не контактируют, и некие намеки на интимность появляются лишь в финале игры между другими героями, Эшли и его антагонистом, Сиднеем. По словам обозревателя, уверенность, с которой прописаны персонажи Vagrant Story, переводит сцены игры из разряда пантомимы в разряд захватывающего театрального представления; Vagrant Story сочетает детально прорисованные исторические декорации с анахроничным дизайном персонажей и их костюмов, привносящим в жанр компьютерной игры «подиумную сексуальность». Изощренная постановка сцен и постоянное движение камеры, по его мнению, позволяют наделить даже самые вяло протекающие сцены внутренним напряжением. Игровая механика сочтена слишком недружественной к игроку — если бы ее освоение было проще, Vagrant Story бы удалось снискать больше поклонников. Дополнительные уровни, открываемые при повторном прохождении, противопоставляются остальной игре: если доступный при первом прохождении контент полностью посвящен рассказываемой истории, то дополнительный — целиком и полностью компьютерная игра, что не позволяет воспринимать Vagrant Story как чистое произведение искусства. Vagrant Story названа «великолепным, невозможным беспорядком», который невозможно повторить или продолжить.

Редакция журнала PSM3 в своем ретрообзоре нашла даже отсутствие озвучивания в Vagrant Story примечательным, посчитав, что насыщенные и прекрасные тексты игры только проиграли бы от произнесения вслух. Авторы обзора противопоставили Vagrant Story как взрослое и серьёзное произведение типичным японским ролевым играм тех времен, с их героями-подростками и примитивными сюжетами. С их точки зрения, боударениельшую роль в создании мрачной и прекрасной атмосферы Vagrant Story играет даже не столько визуальная часть, сколько музыка и звук, и прежде всего настраивающие на нужный лад шумы и шорохи в тишине подземелий. Игровой процесс и прежде всего систему развития оружия авторы обзора назвали глубокими, но «нечестными»: игра не предупреждает, насколько она сложна в этом отношении, и не вникший в развитие оружия игрок может оказаться в безвыходном положении, когда ему остается только начать игру заново.