Last Exile ci racconta un pezzo di storia del mondo di Prester, mondo alquanto particolare nella sua forma, simile ad una clessidra, ai cui estremi si trovano due regni: Anatory e Disith. Questi regni sono separati tra loro dal Grand Stream, un luogo angusto e pericoloso, dando poche  possibilità ai due regni di comunicare. In seguito ad un brusco abbassamento della temperatura e ad un radicale cambiamento delle condizioni climatiche, l'Impero di Disith decide di attraversare il Grand Stream con la sua flotta navale, ed occupare Anatory. Quando inizia la storia i due regni sono ormai da tempo coinvolti in una lunga ed estenuante guerra. Il ruolo della Gilda, figura alquanto emblematica, è quello di supervisionare gli scontri tra i due regni. E' quì che troviamo i nostri protagonisti: Claus Valca e Lavi Head che, seguendo le orme dei rispettivi padri, sono divenuti l'uno pilota di vanship e l'altra il suo navigatore.

Lavorano come corrieri per la Nordkhia Vanship Organization, e, con l'obbligo di portare a compimento una pericolosissima missione (che li condurrà ad unirsi all'equipaggio della nave volante Silvanas), si troveranno ben presto coinvolti nello scontro tra Anatory e Disith.