レッド・デッド・リデンプションはアドベンチャーウエスタンであり、ゲーム「レッド・デッド・リボルバー」の後継に当たります。ゲームの大部分は2011年に行われ、旧西部の衰退期間中の物語が展開されます。主人公ジョン・マーストンは元犯罪者で、元バンドのメンバーを見つけて排除する予定ですが、妻と息子が政府に捕らえられ、マーストンを捕まえるために政府の賞金稼ぎにするために拘束されています。彼には、3人の元仲間を裏切る以外の選択肢はありません。
プレイヤーは周囲の物体とインタラクトし、さまざまな武器を使って敵と戦うことができます。ゲームの主な移動手段は馬で、異なる種が異なる特性を持っていますが、利用するには最初に捕まえて訓練する必要があります。
さらに、プレイヤーは西部探検中に遭遇するさまざまなイベントに参加できます：公開処刑、陰謀、襲撃、銃撃戦、動物の攻撃の防衛など。たとえば、キャラクターがバンドが町を襲撃しているところを見ると、彼らを射撃して、ボーナスを得ることができます。また、プレイヤーは決闘、賞金稼ぎ、ギャンブル、ハーブの収集、毛皮や肉のための動物の狩りにも参加できます。
レッド・デッド・リデンプションはまた、正または負の「名声」を蓄積するための道徳システムを使用します。正の名声を蓄積するには、バンディットを生け捕りにし、彼を殺さないことでか、囚人を解放する必要があります。負の名声は、主人公が犯罪を犯すと、たとえば強盗や無実の市民の殺人を行うことで発生します。また、周りの他のキャラクターの行動にも影響を与えます：彼が負の名声を持っている場合、市民は彼の近くで不安を感じ、保安官は次回の出会いで彼を殺すと約束します。名声がポジティブな場合、市民と保安官は彼を歓迎します。指標が増加すると、賞金稼ぎは彼を殺すことができるか疑問を抱き、人々は逃げます。マーストンはバンダナで名声を隠すことができます。
戦闘では、キャラクターは石の後ろに隠れ、そこから発砲することができます。銃撃戦と火器はゲームの大部分を占めています。すべての銃撃戦は三人称視点で行われます。
また、最大16人のプレーヤーが参加できるマルチプレイヤーモードも用意されています。