事実とフィクションが混在し、実在の歴史的人物が多数登場する。主人公サイラス・グリーブスの記憶に基づく1880年から1910年までの出来事が、彼の回想としてカートゥーン風に映像化されて表現される。彼の誇張や記憶違いによる虚実綯い交ぜのナレーションが、そのままゲーム世界でプレイヤーの目の前で動的に変化する構成となっている。
1910年のカンザス州アビリーン。高名な賞金稼ぎサイラス・グリーブスを名乗る老人が酒場に入り、その場にいた人々（ジャックという皮肉屋、スティーブという古株、バーテンダーのモリーとベン、ドワイトというティーンエイジャー）相手に自分の武勇伝を滔々と語り始める。
エピソード I:ビリー・ザ・キッド
1880年、フリーランスの賞金稼ぎサイラスはニューメキシコ準州に入る。リンカーン郡戦争のさなか、ビリー・ザ・キッドのレギュレーター・ギャングに加勢した。彼が長年追い続けている宿敵ロスコー・ブライアント、通称ボブが、当時ビリーのライバルだったジョン・キニー・ギャングの側にいたためである。サイラスの談によれば、彼はビリーの唯一の援軍として戦闘に参加し、包囲された農家でビリーを助けた。 そこでダーティー・デイブとすれ違い、チャールズ・ボウドレの死を目撃した。 終始劣勢に立たされ、撤退せざるを得なくなった。 サイラスは逃走用の馬を探すことになったが、厩舎でパット・ギャレット保安官に待ち伏せされ逃げ場を失ったビリーとその一味は降伏せざるを得なくなり、全員が逮捕された。サイラスは、ドワイトが言うダイム小説に描かれている、ギャレット保安官を正々堂々と決闘で破ったという描写を真実ではないと断じた。
スティンキング・スプリングスでパット・ギャレットに逮捕されたサイラスは、リンカーン郡の刑務所に移送され、絞首刑を待つ身となっていた。だが思いがけず、サイラスはビリー・ザ・キッドによって解放された。こっそりとは抜け出すことができなかったサイラスは、ボブ・オリンジャー保安官の事務所から奪ったショットガンで、行く手に立ちはだかる敵対者を皆殺しにしながら町を激走する。サイラスによれば、ほとんどの町の人は体格や肌の色が似ていることから、自分をビリーと間違えたという。怒ったボブ・オリンジャーに呼び止められ、決闘を申し込まれたがサイラスはこれに勝利した。こうして派手な脱獄に成功し、再び賞金稼ぎの仕事を続けた。解放されたにもかかわらず、サイラスは自分を救ってくれたビリーに特に感謝もしていなかった。彼は、ビリーに自分の逃避行のための目くらましに利用されただけだろうと考えていたので。
エピソード II: カウボーイズ
あれからサイラスはメキシコに渡り、ルーラルズ（メキシコ政府の準軍事組織）で働いていた。 グアダルーペの渓谷にて、手遅れでニューマン・クラントンが率いるコーチス・カントリー・カウボーイズに襲われた駅馬車を救うことができなかった。サイラスは高台から"アパッチ・スタイル"で山賊どもと交戦した。 サイラスはできる限り撃ち殺したが、やがて弾薬不足に陥った。 やむなく洞窟に逃げ込み、全力疾走してインディアンの戦士の死体を見つけ、そこから必要な弾薬とダイナマイトを取り戻した。 この奇跡的とも思える出来事が流れを変え、サイラスは反撃に転じることができた。 岩を隠れ蓑にしながらサイラスはガトリング銃をクランキングするクラントンを出し抜き、殺害することに成功した。 サイラスは、広く信じられていることとは裏腹に、クラントンの死はワイアット・アープとは無関係だと主張した。
カーリー・ビル・ブロシアスはクラントンが倒れた後にカウボーイズのリーダーとなり、ギャングたちはアリゾナ州アイアン・スプリングスの製材所に移転した。サイラスは彼らを追跡し、巨大な屋敷を抜けて貯木場まで行き、そこでカーリー・ビルと対決したがタフな性格だった。彼の行動は、仲間が逃げるのに十分な時間を稼いだ。カーリーがサイラスに倒されたときには、ボブの知人で手がかりである目当てのジョニー・リンゴはすでにいなかった。結局、リンゴを見つけて殺すのにはさらに数カ月を要した。
エピソード III: ジ・イノセント
意図したわけではなかったが、カーリー・ビルとジョニー・リンゴの殺害により大きな報酬を得たサイラスは、ボブを追い続けるためにはもっと多額の資金が必要だと感じた。その後、彼はモンタナ州バナックの元保安官からの依頼を引き受け、ジ・イノセントと呼ばれる殺人・窃盗団を率いた罪に問われていたヘンリー・プラマーを追跡する。プラマーは鉱山労働者から搾取して一攫千金を狙うという評判だった。特に、プラマーの犠牲者の家族から賞金がプールされていたため魅力のある仕事だった。プラマーは南北戦争の帰還兵である流れ者たちを雇っていて、苦戦を強いられたが勝利を収めた。彼はまた、根城の鉱山に入る方法を見つけなければならない。彼は状況を把握するうちに、坑道を通るのは不可能だという結論に達し、最終的には高所恐怖症を克服して、最も大胆な方法でプラマーにたどり着いた。落とし穴の上からダイナマイトで攻撃されるという不利な状況に陥ったものの、サイラスは優れた射撃の腕前で勝利を収めた。
エピソード IV: ジョン・ウェスリー・ハーディン
ロスコー "ボブ "ブライアントが、西部で最も危険なアウトローの一人であるジョン・ウェズリー・ハーディンと一緒にいるという噂を聞いたサイラスは、カンザス州アビリーンまで追跡した。 サイラスは二人組がそこにいると信じ、町外れのキャトル・キャンプを襲撃。 賊を全滅させたが、死者の中に標的はいなかった。サイラスはブルズ・ヘッド・サルーンへと向かい、ハーディンのバースデイパーティーを台無しにする。やがて血に染まった酒場でサイラスはハーディンに決闘を挑んだ。 集中力と巧みな技で、サイラスはハーディンの放った二丁拳銃12発の銃弾をすべてかわす。 両方の銃が空になり、ハーディンは降伏するしかなかった。 彼は刑務所に入った。
エピソード V: グレイ・ウルフ
結婚式を迎えた娘を白人たちに虐殺されたという、インディアンの酋長の悲劇的な生い立ちを知っていたサイラスは、最初はこの仕事を引き受けることに消極的だったという。 それでも賞金のために引き受けた。アパッチ族のテリトリーをトレッキングしていた彼は谷で待ち伏せを受ける。戦い抜いた後、彼はインディアンの洞窟の隠れ家に入り、洞窟の中でグレイ・ウルフを見つけたが白昼夢を見る。 サイラスはグレイ・ウルフが魔法をかけて幻覚を見せたのだと考えた。 サイラスは幻覚の中で酋長の記憶を垣間見た。 グレイ・ウルフはまた、サイラスは偉大な戦士だが、復讐の考えに溺れすぎると「魂を失う」とも告げようとした。サイラスが白昼夢から立ち直ると再びグレイ・ウルフを捕まえようと外まで追いかけ、それは謎かけの続きを聞くためでもあったが、インディアンの酋長は狼に姿を変えそのまま姿を消した。結果的にサイラスは懸賞金を受け取ることができなかった。
エピソード VI: ダルトン・ブラザース
ドワイトが話題を切り出し、サイラスにダルトン一家を倒すのに果たした役割について尋ねた。ベンは会話に割って入り、自分も武器を取って兄弟の最期を目撃した自警団員の一人であると語った。彼の簡略化されたバージョンでは、ダルトン家全員が銀行内でその場で殺害されたという。これにドワイトは納得せず、サイラスが英雄として描かれたダイム・ノベルで読んだことを語った。正午のこと、ダルトン一家は銀行の向かいのビルから連邦保安官に包囲されていた。膠着状態を打破するため、サイラスは単独で給水塔から飛び降り、屋上から銀行を炎上させた。ダルトンとその子分は全員排除され、サイラスの勝利に終わったという。しかし、その脚本はサイラス自身によって承認されたものではなかった。サイラスの談では実際の戦闘は夕方に行われ、ダルトン一家は銀行強盗を働いて逃げる途中だった。サイラスは彼らを追いかけていってギャングたちを倒した。最後の手段にダルトン一家はローリング・トラップを使ってサイラスを遅らせ、二人のダルトン、ロバートとグラットンを逃がした。ダルトン家の末っ子エメットは後方を援護するために残り、23発も銃弾を浴びたが一命を取り留めたという。
サイラス・グリーブスは、その後もロスコー・ブライアントを執拗に追い続けたことを語る。彼はミズーリ州の沼地をさまよい、ボブの一味を探す。サイラスの探求心は、ボブが彼の兄弟の殺害に関与していたことに起因する、深い個人的なものであった。物語はサイラスがさまざまな場所で手がかりを追い、そのたびにボブとの距離を縮めていくフラッシュバックの連続で展開する。サイラスは、ボブの一味が占拠している難破した蒸気船を発見する。 だがサイラスは罠に嵌められ、燃え盛る船から逃げ出さなければならなくなる。
エピソード VII: ワイルド・バンチ
サイラスは、ボブがあの悪名高いワイルド・バンチ列車強盗団に加わったと聞いていたと言う。ブッチ・キャシディが率いるワイルドバンチは、コロラド州からモンタナ州にかけて銀行や列車を襲う無法者集団だった。その中にはサンダンス・キッドと、そしてボブもいた。その足跡は、オーバーランド・フライヤー号でワイオミング州ウィルコックスに運ばれていた大量の金塊の積荷へと彼を導く。サイラスはジョージ・"フラットノーズ"・カリーを倒したところでボブの痕跡を見失う。5年後、彼はキッド・カリーことハーベイ・アレクサンダー・ローガンの下でギャングが再結集したと聞く。コロラド州まで追いかけてギャングのほとんどを壊滅させたが、キッド・カリーは今頃ボブはブッチ・キャシディ、サンダンス・キッドと一緒に南米ボリビアにいるだろうと言って愚弄する。苛立ったサイラスはキッド・カリーを殺す。
エピソード VIII: ジェシー・ジェイムズ
そしてサイラスの追想は、ボブと並ぶ仇の一人ジム・リードがジェイムズ・ヤンガー盗賊団と行動を共にしていた1881年11月に戻る。ミズーリ州ウィンストン近郊でロック・アイランド鉄道を襲おうとする彼らの企てを中断させた後、サイラスはアウトローのジェシー・ジェイムズと対決し、傷を負わせる。その後、ジェシーの弟フランク・ジェイムズは復讐のためにサイラスを襲った。フランクは丸太小屋からこの襲撃を指揮し、盗賊たちは必殺のスコープ付きライフルで武装していた。それでもサイラスは狙撃をかわし、フランクの小屋をダイナマイトで崖下に吹き飛ばした。フランクは精神を打ち砕かれながらも辛うじて生き残り、サイラスにジムの居場所を教えた。手がかりを追ってサイラスはジムの一味を洞窟で発見した。ジムの子分を皆殺しにした後、決闘でジムを射殺した。ジム・リードの死は、サイラスの復讐リストの中で、ロスコー・ブライアント一人だけがまだ逃走中であることを意味した。
最終エピソード: ワイルド・バンチ リプライズ
時は1910年、現在より半年ほど前のことである。 年老いたサイラス・グリーヴスは、ワイルド・バンチの生き残りが南米からアメリカ合衆国に戻ってきたことを知った。 最後の宿敵ロスコー・ブライアントを見つけようと、サイラスはワイオミング州ウィンド・リバー山脈のどこかにある荒れ果てた町まで一味を追跡した。 ゴーストタウンを縦横無尽に駆け巡る中、サイラスは自分自身の過去の亡霊たちと向き合った。"ボブが殺した数よりも多くの人を殺してきた"と、彼は自らの倫理観に疑問を投げかける。 やがて彼は古い墓地でブッチ・キャシディとサンダンス・キッドと対決する。 その頃、2人のアウトローは富と女の所有権をめぐっていがみ合い、もはや友人同士ではなかった。 互いに銃を構え合うメキシカン・スタンドオフの膠着状態から、サイラスは2人を殺す。ブッチは死に際、ボブは"ベン "という偽名でアビリーンに潜伏していると明かした。
エピローグ
ここまで信じられないような話をした後、ドワイトを含む聴衆全員が、サイラスは単なる嘘つき、ホラ吹き爺だと思い始めた。激怒したジャックは彼を店から追い出そうとする。しかしサイラスは、地味なバーテンダーのベンこそが、ロスコー・"ボブ"・ブライアントであることを確信していた。彼はテーブルの上にカードを並べ、オールド・スパニッシュ・コインを皆の前に置いた。観念したボブは打ちのめされ、慈悲を乞うた。
そしてプレイヤーには2つの選択肢が提示される。赦しか、裁きかー。
呆然としているドワイトに名前を尋ねると、ドワイト・アイゼンハワー（後の陸軍大将、合衆国大統領）だと告げられ、彼が士官学校に行く途中だと知ると、「怒りと悪意で世界を壊すな。築き上げろ。自分の人生でまともなことをするんだ」と諭し、サイラス老人は立ち去って行った。
