Gin no Yuusha e' un manga fantasy ambientato a Totia, un luogo popolato da fate, demoni e guerrieri.
La storia inizia con una promessa fatta tra due amici d'infanzia, Beat e Ricercare (questo nome rivela l'interesse che l'autrice sembra avere per l'Italia). Beat promette di diventare il "guerriero d'oro" mentre Ricercare si impegna a diventare un mago esperto, cosicche' insieme potranno sconfiggere il re dei Demoni e diventare gli Eroi di Totia (nel regno di Totia ci sono diversi ordini di guerrieri: verde, bronzo, argento e oro, quest'ultimo e' ovviamente il grado piu' alto).
Le personalita' dei due amici sono piuttosto diverse: Beat e' un ragazzo allegro, estroverso e un po' testardo, mentre Ricercare e' molto pacato, riflessivo e fin troppo ingenuo. A causa del rarissimo colore dei suoi capelli blu-argentei, Ricercare ha passato un'infanzia infelice e solitaria. La gente del suo villaggio riteneva infatti che il colore dei suoi capelli avrebbe portato sfortuna e alcuni lo chiamavano perfino mostro. Beat era stato l'unico a prendere l'iniziativa e fare amicizia con lui. Oltre a non avere nessun pregiudizio contro di lui, Beat si era complimentato con Ricercare per i bellissimi capelli, e da quel momento i due divennero grandi amici. All'inizio pero' Beat era convinto che Ricercare fosse una ragazza, questo perche' il suo aspetto e' sempre stato decisamente effeminato.
Dieci anni dopo la promessa Beat, che ha ottenuto la qualifica di guerriero d'argento, si appresta a mettersi sulle tracce di Ricercare che a quanto pare sta per terminare gli studi in un istituto di magia ma e' irreperibile.
A Beat giungono delle voci secondo cui l'amico sta aiutando il re dei Demoni, ma credendo che Ricercare sia stato ingannato dal re, Beat continua nel suo viaggio per 'salvare' l'amico dalle grinfie del re dei Demoni.
Quando Beat trova Ricercare, non riesce a credere che il ragazzo stia aiutando di sua spontanea volonta' il 'malefico' clan e lo lascia dopo avergli dato uno schiaffo. Beat, ancora turbato per l'accaduto, incontra un piccolo demone e dopo aver parlato con lui, incomincia a pensare che la propria opinione sui demoni potrebbe essere sbagliata. Così decide di tornare indietro e chiedere a Ricercare il motivo per cui sta dalla parte dei demoni: scopre che non tutti i demoni sono malvagi e che in realta' sono gli umani che li stanno uccidendo solo per la loro origine. Beat e' sconvolto quando viene a sapere che il piccolo demone che ha incontrato e' il re dei Demoni in persona, proprio colui che aveva progettato di uccidere fin da quando era bambino. Il ragazzo decide di cancellare la vecchia promessa: la sua nuova missione sara' riportare la felicita' nel regno dei demoni con l'aiuto dell'amico Ricercare.
Beat diventa presto grande amico di Maou, questo e' il nome del re, il quale ha l'aspetto e la mentalita' di un ragazzino pur avendo piu' di 500 anni.
Ricercare, Beat e Maou intraprendono un viaggio nel quale si trovano ad affrontare diversi pericoli e avventure. Comunque non e' l'azione il fulcro di Gin no Yuusha: l'iniziale atmosfera giocosa viene offuscata nel momento in cui le vite precedenti dei personaggi incominciano a riemergere un po' alla volta.
Beat viene inspiegabilmente trasportato indietro nei secoli, dove incontra una giovane fata marina che gli chiede di accompagnarla a visitare la fata piu' bella, Kuremeia. E' così che vede la bellissima fata imprigionata in un anello magico. Chiunque tocchi quell'anello viene ferito e le fate che cercano di liberarla sono destinate a scomparire. Anche i tentativi di Beat per liberarla si rivelano inutili e alla fine Kuremeia si uccide da sola per evitare che altre persone vengano ferite.
Dopo la morte di Kuremeia, Beat si vede apparire una versione cresciuta di Maou, dal quale apprende che il cuore di Kuremeia ha scelto lui e che d'ora in avanti sara' proprio lui a proteggere la fata. Ma il giorno seguente Beat si risveglia ritrovandosi di nuovo nel presente...
Nel frattempo incominciano ad apparire gli spiriti di sei personaggi del passato, tra cui Seireiou (che in giapponese significa 're delle fate'). Egli possiede una grande forza distruttiva ed e' il creatore di Kuremeia. Intimorito dal fatto che la fata possedesse dei poteri in grado di superarlo, Seireiou incarico' Maou di sigillare Kuremeia nell'anello magico. Lo scopo di Seireiou era impedire alla gente comune e alle altre fate di comunicare con Kuremeia. Quest'ultima venne quindi separata da Kodo, il possessivo ed egoista Eroe di Totia con cui aveva una relazione. Lo spirito di Kodo riappare pero' nel presente con l'intenzione di riprendersi Kuremeia: e' così che viene rivelato che Ricercare e' la reincarnazione della fata!
Per raggiungere il proprio scopo, Kodo si impossessa del corpo di Reseru, l'attuale principe di Totia, che non puo' far niente per impedire che lo spirito lo usi per uccidere il proprio padre, il re, e per diventare il nuovo sovrano. Raggiunta questa posizione, Kodo incarica degli uomini di prendere Ricercare; la sua operazione ha successo dal momento che Ricercare e Beat si trovano lontani l'uno dall'altro. Da questo punto in poi la storia si fa sempre piu' appassionante, arricchita da colpi di scena e dall'entrata di nuovi personaggi...