Mega Man Legends utspelar sig långt efter händelserna i alla tidslinjer. Serien följer den föräldralöse Mega Man Volnutt, hans mekaniska apvän Data, och deras adoptivfamilj Roll och Barrell Caskett medan de söker efter skatter, slåss mot pirater, och upptäcker forntida fiender.

Serien utspelar sig i en värld kallad Terra, som till största delen är täckt av vatten. Detta innebär att det inte finns mycket landyta kvar, och människorna bor därmed på små isolerade öar. Under vattenytan existerar dock en helt annan värld, en mörk, mystisk och forntida värld som är bebodd av farliga maskiner kallade Reaverbots. Människorna kämpar för sin överlevnad, och det enda som kan hjälpa dem att överleva är de så kallade Quantum Refractors, som endast finns att hitta i detta underjordiska rike.

De som vågar sig ner hit kallas Diggers, och de reser via luftskepp mellan öarna för att utforska ruinerna. Olyckligtvis förbrukar dessa luftskepp många Refractors, så jakten på dessa pågår ständigt. Tyvärr finns det också de som letar efter Refractors för egen behållning, vilket även innebär att de stjäl från andra Diggers, och de har fått samlingsnamnet luftpirater.