La historia de "Red Dead Redemption" discurre en los últimos años del Viejo oeste, en 1911, y narra la historia del antiguo bandido John Marston, que es chantajeado por los agentes federales que tienen amenazada a su familia para que imponga la ley en la frontera mexico-estadounidense y capture a su antiguo compañero, y actual bandido, Bill Williamson.