Le jeu démarre et on retrouve le protagoniste de l'histoire, le capitaine Alex Mason, attaché à une chaise, placé devant des écrans de télévision, se débattant et hurlant pendant qu'une voix mystérieuse lui répète : "Les nombres Mason, que signifient-ils ?". Cette phrase, vous allez l'entendre encore et encore au cours du jeu (et pas uniquement celle-ci, d'ailleurs), à tel point que les joueurs s'en souviennent encore aujourd'hui.

A chaque question de cette mystérieuse voix, Mason répond par des insultes. Car oui, le protagoniste dans la saga Black Ops parle, ceci permettant d'améliorer de manière significative la personnalité du héros même si, pour d'autres joueurs, cela casse l'immersion. Il est bon de noter que l'idée de faire parler le protagoniste dans le mode Campagne avait été abordée dans World at War sans avoir été complètement intégrée au jeu.

Un premier flash-back s'enclenche. La quasi-totalité du jeu est une succession de flash-back, s'emboîtant parfois les uns dans les autres. Ce n'est pas la première fois que ce système est utilisé en dehors d'une traditionnelle mission comme dans les précédents opus. Call of Duty 2 : Big Red One utilisait cette même technique pour raconter son histoire.

Le joueur est tout d'abord transporté à Cuba en 1961, au début du débarquement de la baie des Cochons. C'est ici qu'il fait la connaissance du sergent Frank Woods et de Joseph Bowman. Leur mission est simple : éliminer Fidel Castro. Arrivés à la villa d'El Comandante, Woods et Mason s'introduisent dans sa chambre et l'éliminent d'une balle en pleine tête. Malheureusement la mission est compromise et Mason décide de se sacrifier en restant sur place pour protéger la fuite de l'équipe. Il se fait capturer et tombe nez à nez avec... Fidel Castro accompagné de deux officiers soviétiques devant un cargo nommé le Rusalka (Treyarch joue ici sur la légende des doublures et des dizaines de tentatives d'assassinat organisées contre le dirigeant cubain). Fidel Castro est l'une des personnalité historiques que l'on rencontre au cours du jeu.

Mason se retrouve ainsi enfermé pendant deux ans jusqu'en 1963 dans un camp de travail au nord-ouest de l'Union soviétique, à Vorkuta. C'est ici qu'il rencontre Viktor Reznov, personnage déjà aperçu dans World at War. Car oui, les origines de la saga n'ont pas commencé avec Black Ops mais bien avec le cinquième épisode de la série dont on retrouve des références un peu partout au cours de la campagne. Reznov et Mason échafaudent un plan pour s'évader de Vorkuta et pour permettre à Mason de regagner l'Ouest, malheureusement Reznov ne peut faire de même (Treyarch s'est ici inspiré du soulèvement de Vorkuta qui s'était déroulé dix ans plus tôt en 1953).

Le Pentagone, quelques minutes avant une rencontre inattendue.

Mason fait la connaissancee de l'agent Jason Hudson au Pentagone. Au cours de cette visite, il s'entretient également avec John Fitzgerald Kennedy qui l'informe que l'un des officiers soviétiques présents à Cuba, le général Nikita Dragovich, est une sérieuse menace pour les Etats-Unis. Pendant la rencontre, Mason a des crises hallucinatoires, et s'imagine en train d'éliminer le président.

C'est ainsi que Mason et Woods se rendent au centre de lancement de Baïkonour où devait se trouver Dragovich. Ils rencontrent alors le second officier présent à Cuba, le colonel Lev Kravchenko, en train de torturer un agent infiltré, Grigori Weaver. Décidés à récupérer leur coéquipier, Mason et Woods s'infiltrent dans la base, et les joueurs découvrent à cette occasion une nouvelle arme de la série : l'arbalète. Ils finissent par retrouver Weaver désormais borgne, et se dirigent vers la zone de lancement. N'ayant pu empêcher le lancement d'une fusée, ils la font exploser en plein vol et doivent abandonner la mission sans avoir trouvé de traces de Dragovich.

C'est ensuite à la bataille de Khe Sanh, en 1968, que l'on retrouve Mason, Woods, Hudson et Bowman en train de repousser les assauts de l'armée nord-vietnamienne. Toujours pendant l'offensive menée par l'ANV, Mason et son équipe doivent récupérer un défecteur russe possédant des informations capitales avant d'évacuer la ville de Huế. Après avoir parcouru une bonne partie de la ville, Mason tombe enfin sur le défecteur qui n'est autre que... Reznov. Ce dernier lui apprend que Dragovich prépare une attaque massive sur l'Occident avant de prononcer cette phrase : "Dragovich, Steiner, Kravchenko, tous doivent mourir."

C'est à ce moment que la tournure de l'histoire change. Nous ne contrôlons plus Mason mais bien Reznov au cours d'une mission qui se révèlera tragique et dont l'issue formera la clé de voûte de toute la campagne.

Nous sommes en octobre 1945 dans le cercle arctique. Le capitaine Reznov a une équipe composée entre autres de son meilleur ami et frère d'armes, Dimitri Petrenko, qui n'est autre que le protagoniste de la campagne soviétique de World at War. Ils obéissent aux ordres directs de Dragovich et de Kravchenko. Les tensions entre Reznov et les deux officiers sont déjà bien visibles. Leur mission n'a qu'un seul but : capturer vivant le docteur Friedrich Steiner, un scientifique nazi prêt à collaborer avec l'Union soviétique.

Après des combats d'une extrême violence, Reznov réussit à capturer Steiner et à l'amener à Dragovich. Pendant que les derniers soldats SS sont exécutés par Kravchenko, le docteur Steiner guide les Soviétiques dans un cargo échoué tout en expliquant que durant les dernières années de la guerre le troisième Reich a mis en place un programme d'armement inédit dont une des armes est un gaz neuro-toxique appelé le Nova 6. Il était d'ailleurs prévu d'envoyer des missiles sur les principales villes alliées mais la reddition de l'Allemagne annula toute l'opération.

Viktor Reznov, un homme qu'on suivrait même en enfer.

Dragovich voulant voir les effets de ce gaz, il fait alors enfermer l'équipe de Reznov dans des chambres de test. Reznov est alors coincé d'un côté et Dimitri de l'autre. Reznov voit son meilleur ami mourir sous ses yeux dans d'atroces souffrances en quelques secondes. Alors que tout semble perdu, il est sauvé in extremis par l'intervention d'un commando de SAS également intéressé par le Nova 6. Profitant de la confusion et des combats, Reznov arme les quelques missiles encore présents dans le cargo et le coule, espérant ainsi ne jamais revoir l'arme qui a pris la vie de son ami et les hommes qui en sont responsables. Malheureusement, il est capturé et envoyé dans le camp de travail de Vorkuta.

Maintenant que l'existence du Projet Nova est révélée, la CIA envoie les agents Hudson et Weaver pour récupérer le docteur Daniel Clarke à Kowloon, à Hong Kong. Ce dernier est une des personnes responsables de la création du gaz neuro-toxique. C'est durant cette mission qu'une scène a fait quelque peu polémique puisqu'il est possible de torturer Clarke en coinçant un morceau de verre dans sa bouche avant de lui frapper la machoire à plusieurs reprises. Clarke révèle l'existence de "nombres" sans pouvoir en expliquer l'origine puisqu'il est tué au cours de la mission.

Mason, Woods, Reznov et Bowman sont envoyés au Vietnam pour enquêter sur la présence de troupes soviétiques soutenant les vietcongs. Dans les galeries utilisées par les vietcongs, Mason retrouve Reznov et discute avec lui, ce qui perturbe l'intéressé qui lui dit au passage : "Qu'est-ce qui va pas chez vous ?". Mason découvre alors dans les tunnels une planque de Kravchenko où se trouvent des dossiers et des enregistrements sur les tests du Nova 6 dans la région. Par la suite, ils sont envoyés au Laos pour retrouver un avion-cargo qui serait potentiellement rempli de Nova 6. Après une petite séquence en bateau avec "Sympathy for the Devil" des Rolling Stones en fond sonore, ils arrivent à bord de l'avion cargo. L'équipe ne trouve rien mais est capturée par des soldats soviétiques et vietnamiens sous les ordres de Dragovich et de Kravchenko.

Fidel Castro et Nikita Dragovich.

De son côté, Hudson continue d'enquêter sur le Nova 6 et suit la piste laissée par Clarke indiquant une base de recherche secrète dans l'Oural, en Russie. Il est tout d'abord aidé par un duo de pilotes (contrôlé par le joueur) à bord d'un SR-71 qui le guide depuis le ciel. Après avoir infiltré un premier avant-poste et déclenché une avalanche qui manque de les tuer, Hudson et Weaver, accompagnés d'autres agents, s'infiltrent dans la base. Une fois arrivés dans le bureau de Steiner, les portes se bloquent et ils font face à un ultimatum. Steiner est prêt à collaborer avec eux en échange de quoi ils protégent sa vie. Steiner n'est cependant pas présent sur la base, mais sur l'île de la Renaissance, en mer d'Aral.

De son côté, Mason, Bowman et Woods sont en mauvaise posture, piégés comme des rats. Mason est conduit à une table où il peut voir les derniers instants de Bowman avant qu'il ne se fasse éclater l'arrière du crâne. C'est ensuite au tour de Woods quand les goêliers soviétiques et vietnamiens décident de faire une partie de roulette russe. S'ensuit une scène directement inspirée par le film Voyage au bout de l'enfer de Michael Cimino sorti en 1979.

Woods passe en premier et survit. C'est au tour de Mason, mais ce dernier tire sur le soldat qui se trouve à ses côtés avant de récupérer son arme ainsi que celle de Woods. Pendant leur fuite, ils trouvent un hélicoptère soviétique et décident de venger la mort de Bowman. Pendant leur vol, ils découvrent la cachette de Kravchenko et attaquent la base. Très tôt après l'attaque, Mason libére des prisonniers parmi lesquels se trouve... Reznov. Ils prennent d'assaut la base et arrivent au bureau de Kravchenko qui se fait alors sauter avec une ceinture d'explosifs. Mais Woods réussit à éloigner Kravchenko avant la déflagration, sauvant au passage la vie de Mason. Reznov réapparaît alors et demande à Mason s'il est prêt à se venger. Ils trouvent ensuite des documents sur Steiner et l'île de la Renaissance. "Dragovich, Steiner, Kravchenko, tous doivent mourir".

Arrivés sur l'île, Reznov et Mason découvrent tout un complexe et s'y infiltrent pour dénicher le docteur Steiner. Ils se rendent vite compte que la CIA est également sur les lieux et que cela pourrait les compromettre. Mason et Reznov arrivent finalement dans la salle où se trouve Steiner, et Reznov l'élimine alors d'une balle dans la tête. "Mon nom est Vitkor Reznov... et j'aurai ma vengeance !"

De leur côté, Hudson et Weaver sont également présents sur l'île et se fraient un chemin tout en combattant les forces soviétiques présentes. Le Nova 6 est lâché sur eux mais ils réussissent à mettre leurs masques avant qu'il ne soit trop tard. Ils atteignent alors le complexe pour voir à leur plus grande surprise Mason pointer un pistolet sur le docteur Steiner et l'abattre froidement. Ils ont tout juste le temps d'attraper Mason et de l'assommer.

Finalement l'identité de la voix mystérieuse se révèle au grand jour : il s'agit de Jason Hudson. Il commence à détacher Mason lorsque ce dernier, pris d'une crise de délire, le frappe au visage et s'enfuit. Il erre ainsi dans les couloirs du Pentagone, imaginant Reznov sur les écrans, voyant des fusées décoller en plein milieu des couloirs et des nombres, beaucoup de nombres. Puis un nouveau flash-back a lieu, durant lequel on comprend que Steiner et Kravchenko ont lavé le cerveau de Mason à Vorkuta mais que Reznov a aussi en partie saboté leur plan pour y mettre son objectif, qui est de venger Dimitri Petrenko.

Les nombres, morceaux d'un vaste plan.

Hudson retrouve Mason et lui fait comprendre que Reznov est mort 5 ans auparavant et qu'il hallucine depuis le début. Hudson fait écouter à nouveau les numéros et Mason arrive enfin à se souvenir de ces nombres retransmis depuis le cargo Rusalka qu'il avait déjà aperçu à Cuba. Ces nombres sont des codes pour des agents dormants aux Etats-Unis qui eux aussi ont subi un lavage de cerveau. Ces codes leur indiquent où et quand ils doivent libérer le Nova 6.

Hudson, Mason et Weaver se rendent dans le golfe du Mexique avec plusieurs autres agents pour en finir avec Dragovich. Après s'être frayé un chemin jusqu'au coeur du navire, ils se rendent compte que le cargo n'était qu'une "antenne" et que la véritable source de transmission est une base sous-marine. C'est ici que Dragovich s'est réfugié. Après avoir arrêté la transmission, Mason attrape Dragovich. Il lui dit que le lavage de cerveau qu'il a subi pour essayer de tuer le président Kennedy a échoué. Dragovich, hilare, répondit "Essayé ?".

Mason et Hudson peuvent finalement remonter à la surface, mais avant de l'atteindre Mason entend une dernière fois Reznov : "Tu l'as fait, Mason... Tu as fait ce que je n'ai pas pu faire". Weaver récupère Mason et Hudson, la menace est enfin éliminée.

Les dernières images du jeu nous montrent un extrait de film où l'on peut voir le président Kennedy à Dallas. L'image se fige et un zoom laisse apercevoir parmi la foule un visage similaire à celui de Mason.