In der bisweilen recht unlogischen Hintergrundgeschichte schlüpft der Spieler in die Rolle eines Nomaden, der zusammen mit zwei weiteren Schatzgräbern einem lukrativen Geschäft nachjagt. Mit kleinen Flugzeugen fliegen die Nomaden durch das märchenhafte Wolkenuniversum, als sie plötzlich von Angriffsjägern attackiert werden. Eines der Nomadenschiffe wird von einem Schuss gestreift und stürzt auf einem der Planetenbruchstücke ab. Der Pilot überlebt und trifft, während er die Insel durchstreift, auf einen der legendären Baumeister. Dieser klärt ihn über den Umgang mit mächtigen Artefakten auf und hilft dem Nomaden beim Kampf gegen die übermächtigen Angreifer. Diese Hilfe ist jedoch nicht ganz uneigennützig, wie sich später herausstellen soll.

Ab jetzt übernimmt der Spieler die Kontrolle über seine aus der Third-Person-Perspektive zu steuernde Spielfigur. Mit Hilfe der Artefakte kann der Nomade verschiedene Bauwerke auf seiner Insel errichten. Ein Leuchtturm beispielsweise ermöglicht es ihm, die Insel zu freigeschalteten Navigationspunkten durchs Wolkenmeer zu steuern. Mittels mächtiger Kanonen und Jagdflieger kann er Angriffswellen trotzen oder feindliche Inseln erobern. Es ist sogar möglich, selbst die Steuerung eines Jagdfliegers zu übernehmen und feindliche Stellungen anzugreifen. Im Laufe der Geschichte baut der Spieler seine Insel mit immer mächtigeren Waffen und Verteidigungsanlagen aus. Bisweilen kann er sogar so weit an eine fremde Insel heranmanövrieren, dass die Spielfigur zu ihr hinüberspringen und sie zum Fuß erkunden kann. Zur Verteidigung stehen ihr dort Energiebälle oder Sprengstoff zur Verfügung.

Auch bei der grafischen Umsetzung lässt Project Nomads keine Wünsche offen. Ohne Sichteinschränkung präsentiert sich dem Spieler eine farbengewaltige 3-D-Welt mit riesigen, durchs Wolkenmeer treibenden Bruchstücken des ehemaligen Planeten und den Ruinen uralter Bauwerke. Die eindrucksvollen Explosionen und Lichteffekte überzeugen selbst verwöhnteste Computerzocker. Spielerisch ist Project Nomads dagegen nicht ganz so ausgewogen. Viele Missionen sind vom Handlungsablauf recht gleichartig und ziehen sich mitunter unnötig in die Länge. Durch die eindrucksvolle Spielwelt, die ungewöhnliche Hintergrundgeschichte und die intuitive Spielsteuerung zählt Project Nomads trotz kleinerer Macken zu den innovativsten Spielen des Genres.