V bojové akci s RPG prvky X-Men Legends na mobilní platformu Nokia N-Gage hráč velí skupině čtyř mutantů, ale najednou může ovládat vždy pouze jedinou postavu. Všechny členy týmu si hráč může vybrat z celkem jedenácti hratelných postav, mezi nimiž nechybí Wolverine, Kyklop nebo Bouře.

Mladá mutantka Alison Crestmere má schopnost ovládat zemské magma, a tak jí mutanti, kteří jsou věrní momentálně uvězněnému Magnetovi, chtějí unést, osvobodit Magneta a uskutečnit jeho ďábelský plán na ovládnutí světa. X-Menům Wolverinovi a Kyklopovi se jí však podaří zachránit a přivést do Xaverova institutu, kde se vycvičí v X-Mena a dostane jméno Magma. Nebezpečí ze strany Magnetových stoupenců však stále trvá, a tak je třeba obezřetnosti.

Ovládané postavy mohou při boji s nepřáteli provádět komba a získávají také zkušenostní body, které hráč může rozdělovat mezi čtyři primární schopnosti a jedinečné dovednosti každého mutanta. K dispozici je i inventář, kam se ukládají získané předměty a vybavení. Ty lze buď prodat v X-Mansion anebo jimi vybavit některou z postav, které poté narostou některé atributy.

Celkem je třeba splnit čtyřiadvacet misí a mimo režimu pro jednoho hráče hra nabízí i kooperativní multiplayer až pro čtyři hráče pomocí bezdrátového připojení Bluetooth.