Die Story handelt von Manuel Calavera, oder auch Manny, der Aushilfs-Grimreaper. In einer lateinamerikanisch angehauchten Welt der Toten arbeitet er gezwungenermaßen im Department of Death. Diese besondere Ehre wurde ihm zuteil, da er in lebendiger Form zu wenig gute Taten vollbrachte. Ironischerweise ist er nun dazu gezwungen neue Ankömmlinge in der Welt der Toten die Fahrt in das gelobte Reich zu organisieren. Zur Auswahl steht die Reise zu Fuß, per Auto oder Schiff sowie über den Zug Nummer Neun. Je nach Gütigkeit des Verstorbenen wird dieser also auf eine vierjährige Fußreise geschickt oder ihm ein Zugticket für die Nummer Neun in die Hand gedrückt, die nur vier Minuten für dieselbe Strecke benötigt. Doch alsbald sorgt Domino Hurley, der neue Arbeitskollege von Manny, für Unstimmigkeiten. Verstorbene mit hervorragendem Lebenslauf scheinen keine Kandidaten für die Nummer Neun zu sein. Als unser Alter-Ego der Sache nachgeht, wird er kurzerhand für seine Rumschnüffelei gefeuert und kommt mit dem Revoluzzer Salvador Limones in Kontakt. Zusammen mit der Untergrundbewegung Guerilleros wollen sie die Korruption innerhalb des Department of Death bekämpfen.
Entwickler Tim Schafer bediente sich vielerlei Inspirationsquellen. Die Mythen der aztekischen Totenkultes, die Atmosphäre der Filme aus den 1930ern, der düstere Plot eines Film Noir, dem Zeichenstil von Hugh Ferris und dem lateinamerikanischen Soundtrack von Peter McConnel. Außerdem erwähnte er in Interviews oft die Filme The Maltese Falcon on the Waterfront, Double Indemnity und Casablanca als Vorlagen für seine Ideen. Das Charakterdesign erinnert an sogenannte Calaveras, welche in Mexiko zu erstehen sind. Diese stellen keine Skelette dar, sondern personifizierte Seelen. Das ganze Spiel wirkt dadurch düster, atmosphärisch und könnte glatt aus der Feder von Filmregisseur Tim Burton stammen. Lustigerweise ging damals sogar das Gerücht um, er würde an einem Film zu Grim Fandango arbeiten, doch stellte sich dies als Ente heraus.
Durch verschiedene Kameraperspektiven innerhalb desselben Raumes wollte man das ehemalige Point‘n‘Click Adventure auf eine dramaturgisch neue Stufe heben. Doch natürlich hatte die schicke Optik einen großen Haken. Gesteuert wurde erstmals nicht mit der Maus, sondern per Tastatur oder Gamepad. Dies hatte zur Folge, das die Steuerung sehr ungenau und krampfig vonstattenging.