Direkt nach der Veröffentlichung von Outcast Mitte 1999 starteten die Entwickler mit der Sammlung erster Ideen für einen Nachfolger, um den Publisher Infogrames zur raschen Finanzierung der Vor-Produktion des Sequels zu überzeugen. Da Infogrames viel in Appeal und Outcast investiert hatte, waren die Geldgeber auch zur Finanzierung eines Nachfolgers bereit. Die eher enttäuschenden Verkaufszahlen des Originals von insgesamt ca. 400.000 Einheiten lagen weit unter den Hoffnungen von Infogrames zurück. So schaffte es Outcast zwar seine Kosten wieder einzuspielen, der Millionenerfolg blieb jedoch aus.

Eine der Folgen war, dass Infogrames den Nachfolger primär für Konsolen entwickeln wollte und der PC nur die Zweitplattform sein sollte. Außerdem sollte der Action-Anteil deutlich steigen und das Adventure-Gamplay in den Hintergrund rutschen. Besonders Yves Grolet war mit dieser Entwicklung sehr unzufrieden. Der Deal mit Infogrames finanzierte schließlich die Vor-Produktionsphase inklusive der Entwicklung neuer Technologien und des grafischen Designs.

Da sich die Playstation 2 zur erfolgreichsten Konsole dieser Generation entwickelte, wurde sie vom Publisher als primäre Plattform ausgewählt. Wieder war Yves Grolet nicht einverstanden, da die Xbox eine damals technisch überlegene Konsole war.
Die Entscheidung, für die Playstation 2 zu entwickeln, stellte sich als große technische Herausforderung dar, da die Entwickler auf den PC spezialisiert waren. Anfangs gab es viele Performance Probleme und technische Schwierigkeiten. Yves Grolet entschloss sich daher im Jahr 2000, Appeal zu verlassen und mit seinem eigenen Studio Elsewhere Entertainment an anderen Projekten für die Xbox zu arbeiten. Die Nachbesetzung für Yves Grolet stellte sich erst spät als Fehler heraus, wodurch das Design mehrmals geändert werden musste und viel Zeit verloren ging.

Für das Spiel wurde eine neue, hauseigene Grafik-Engine namens Himalaya programmiert, welche im Unterschied zum ersten Teil komplett polygonbasiert war und auf Voxel-Technologie verzichtete. Trotz der Herausforderungen gelang es dem Team, das Demo in 60fps flüssig auf der Playstation 2 zum Laufen zu bringen. Der ursprüngliche Vertrag über 7 Millionen Euro wurde aufgrund finanzieller Probleme des Publishers schließlich auf 5 Millionen reduziert. Trotzdem gelang es den Entwicklern einen voll funktionierenden Prototypen zu entwickeln. Auch wenn bereits viel Arbeit an den Umgebungen und dem Universum des Spiels abgeschlossen war, befand sich das Spiel noch in einem frühen Entwicklungsstadium und war noch recht weit von einer Veröffentlichung entfernt. Ein Video des Demo-Levels wurde erst Jahre später von Franck Sauer veröffentlicht.

Nach schweren finanziellen Einbußen am Aktienmarkt von Infogrames im Jahr 2001 wurden praktisch alle 3rd-Party-Projekte eingestellt, um Finanzmittel für das interne Eden Studio zusammen zu bekommen. Outcast – The Lost Paradise wurde so nach 2 Jahren Entwicklung und Ausgaben von ca. 3 Millionen Euro eingestellt. Da Infogrames Miteigentümer von Appeal war, wurde das Studio nicht sofort geschlossen.

Im Austausch gegen einen neuen Vor-Produktionsvertrag für ein Spiel zur Comic-Serie Tim und Struppi verkaufte Infogrames alle Anteile an Appeal zurück. Die Studiochefs Yann Robert und Franck Sauer hatten keine andere Wahl als dem Deal zu zustimmen. Der Prototyp für Tim und Struppi wurde zwar 2002 fertig gestellt, doch es erfolgte kein weiterer Auftrag zur Fertigstellung des Spiels. Aus diesem Grund ging das Studio dann im August 2002 endgültig insolvent. Yann Robert und Franck Sauer gelang es, einen Großteil der Spiel-Assets, wie die unfertige Grafik-Engine, zu kaufen und so später mit ihrer neuen Firma Fresh3D einige kleinere Spiele zu veröffentlichen.