Hoewel de trailer van Call of Duty 4 enig informatie gaf over het verhaal van de game, werd op een exclusieve demonstratie van de game in Engeland pas duidelijk wie de hoofdrollen zouden vervullen. Grant Collier van Infinity Ward verklaarde dat ze hun eigen conflict hebben verzonnen met in de hoofdrol een hele slechte Russische ultranationalistische, genaamd Zakheav, die de Sovjetunie in de stijl van zijn idool Stalin wil terugbrengen.  

Zakheav wordt gesteund door een belangrijke groep van Russische zakenlieden, mensen uit de maffia en het leger waardoor hij in staat is om een burgeroorlog in eigen land te beginnen. Echter weet Zakheav dat andere machten uit de wereld uiteindelijk betrokken zullen raken bij dit conflict. Daarom broedt hij op een manier om de grootste bedreiging – de VS – te omzeilen. 

‘’Iedereen weet dat Amerika een uitloper is in het conflict rondom het Midden Oosten,’’ verklaart Collier. Daarom gebruik Zakheav zijn vriend Al-Asad die in het Midden Oosten een (gefinancierde) staatsgreep uitvoert. Het is een val waardoor de Amerikanen klem worden gezet en Zakheav blij is. 

Ondertussen hebben de Britten, in vorm van speciale SAS troepen, Zakheav al voor een lange tijd - sinds hij wapenhandelaar was – strak in de gaten gehouden. Ze zijn in het geheim bezig om hem in Rusland te vinden. Daarnaast proberen ze door, al samenwerkend met enkele Russen, meer informatie te verzamelen om de VS te van overtuigen dat de oorlog in het Midden Oosten slechts een afleiding is. 

De Amerikanen sturen een eliteafdeling van de Marine – genaamd Force Recon – om Al-Asad op te sporen. Dat zal uiteindelijk leiden tot twee verhaallijnen die in Rusland tot elkaar komen. Jouw missie: het opsporen van Zakheav, Al-Asad en hun twee dichte vennoten (die gezamenlijk de ‘The Four Horsemen’ vormen) en ze te stoppen voordat de wereld in een catastrofaal en vernietigend conflict is verbonden. Collier maakte duidelijk dat het verhaallijn geen betrekking heeft tot de oorlog in Irak.