Yhteenveto
Satoja vuosia ennen Starsiege: Tribes -pelin tapahtumia sijoittuva Vengeance kuvaa kasvavan heimosodan alkua. Se keskittyy viiden eri hahmon ympärillä pyöriviin tapahtumiin kahden sukupolven ajan ja siihen, miten kukin heistä vaikuttaa sodan kehitykseen. Tarina ("Menneisyys") alkaa, kun Phoenix-alaklaanin johtaja Daniel sieppaa tulevan kuningattaren, prinsessa Victorian. Hän vie Victorian kotiplaneetalleen näyttääkseen, mitä vääryyksiä hänen kansaansa on kohdistettu, ja lopulta he rakastuvat toisiinsa. Tänä aikana kybriditappaja nimeltä Mercury saa tuntemattomalta toimeksiantajalta tehtäväkseen eliminoida Daniel, mutta sopimus perutaan juuri ennen kuin laukaus ammutaan. Lopulta Victoria ja Daniel yrittävät sopia asioita keisarillisten ja Phoenixin välillä, mutta kaikki päättyy katastrofaalisesti, kun Phoenixin viholliset, Blood Eagle -heimo, tekevät hyökkäyksen Phoenixin tukikohtaan tekeytyen keisarillisiksi joukoiksi. Raivostuneena Daniel tappaa keisarillisen kuninkaan, Tiberiuksen, ja Victoria puolestaan kostaa tämän tappamalla Danielin. Lopulta paljastuu, että Victoria oli raskaana Danielin lapselle, joka syntyy pian tämän jälkeen tyttönä ja saa nimekseen Julia.