La Historia de Vagrant Story arranca cuando Ashley Riot, un Riskbreaker (Soldados de élite a los que asignan misiones de gran riesgo) de la VKP (Valendia Knights of Peace/Caballeros de la Paz de Valendia) es enviado por decisión del parlamento a la residencia del Duque Bardorba. En esta introducción/tutorial, el protagonista, Ashley Riot, se infiltra en la mansión durante la ocupación de unos fanáticos religiosos seguidores de un culto llamado "Müllenkamp" y consigue alcanzar a su líder, el enigmático y andrógino Sydney Losstarot, a quien hiere en el corazón con una flecha antes de que éste escape con Joshua Bardorba, el hijo menor del Duque, e intenta distraer a Ashley con su Wyvern D'Tok.

El culto se refugia entonces en la cercana Léa Monde (El Mundo), una ciudad milenaria de la que se cuentan inquientantes leyendas acerca de sus (codiciados) poderes sobrenaturales. Ashley, con la ayuda de la agente/inquisidora Callo Merlose, alcanza la ciudad mediante las catacumbas subterráneas, pero no son los únicos que rastrean a los seguidores de Müllenkamp. La iglesia personificada en el Cardenal envía a su brazo armado, los Crimson Blades, comandados por el despiadado Romeo Guildestern para erradicar a los herejes con la aparente colaboración de otro Riskbreaker que envía la VKP cuando da por perdido a Ashley: Rosencrantz. Así da comienzo esta obra magistral , una auténtica joya de PS , que a lo largo de más de 40 horas de auténtico disfrute nos llevará por giros inesperados, traiciones, magia, conspiraciones e hipocresía en las que veremos cómo todas las facciones en conflicto intentan alzarse con el objeto del deseo: el secreto de la vida eterna que está bajo sus pies, y la llave secreta para acceder a ella.

El estilo gráfico del juego es muy oscuro y enfatiza en tonos marrón, lo que añade un sentimiento de misterio. El estilo de secuencias cinematográficas es similar al utilizado en Metal Gear Solid: en ambos juegos las secuencias fueron renderizadas con el engine del juego con un fuerte sentido cinematográfico.

En un sentido amplio, Vagrant Story es un reto solitario que se desarrolla en calabozos, en el cual Ashley explora las ruinas de la ciudad de Leá Monde y sus cavernas y catacumbas. Los caballeros de Crimson Blade patrullan las calles arriba, en busca de Sydney; los corredores abajo están infestados de bestias, duendes, fantasmas y muertos vivientes.

El sistema de batalla obliga al jugador a encadenar diferentes ataques para lograr combinaciones (combos) largos e infligir daño en el enemigo. Esto se realiza presionando los botones en una sucesión; de esta manera, el combate casi asemeja a un juego rítmico. El jugador puede apuntar a diferentes partes del cuerpo, y el daño se realiza de acuerdo a la parte del cuerpo atacado y a la afinidad del arma usada por Ashley. Entre más pelee, más alto se eleva su nivel de Riesgo, haciendo difícil su concentración, bajando su precisión pero incrementando sus golpes demoledores. Las habilidades de Defensa permiten a Ashley a reducir o rebotar el daño o evitar estados alterados; una variedad de hechizos pueden ser utilizados, para atacar, curar e incrementar o decrementar atributos. Finalmente, existen las Break Arts, ataques poderosos que pueden ser realizados a cambio de los hit points de Ashley.

En adición a la pelea, Ashley puede correr, brincar y empujar una variedad de bloques y canastas para poder pasar obstáculos o usarlos como plataforma. Durante el curso del juego, el jugador se enfrentará a una serie de enigmas con bloques que necesitarán ser resueltos para poder avanzar. Cuando el jugador regresa a cualquier lugar donde el enigma ya ha sido resuelto, un modo de juego contra reloj llamado "Evolve or Die" empezará, y tendrá que alcanzar el final de la sala resolviendo el enigma en el menor tiempo posible.

El sistema de creación de Vagrant Story se podría considerar como un juego aparte. En áreas de trabajo designadas, el jugador puede crear y modificar armas y armaduras a su gusto, con diferentes rangos, poder y estadísticas. Todas las armas caben dentro de una de las tres categorías: punzantes, cortantes y contundentes. Además, hay seis tipos de afinidades de criaturas y ocho tipos de afinidades de elementos. Las armas obtienen afinidades de los enemigos que las usan para atacar; las armaduras las obtienen de los ataques que reciben. Lo que un arma o armadura obtiene en un área lo perderá en otra, por lo que ningún arma o escudo es igualmente efectiva contra todos los enemigos. De todas formas, las armas y armaduras poderosas pueden ser combinadas y unir sus afinidades (y hasta crear un nuevo tipo de arma o armadura). La clave para derrotar a la mayoría de los enemigos es tener el tipo correcto de arma; las afinidades inherentes añaden un extra, pero no son tan importantes como las gemas que mejoran las afinidades o hechizos que un arma tiene.