The story begins in 1993 in Somalia when Elliot Salem and Tyson Rios (the protagonists of the game) are still in the U.S. 75th Ranger Regiment, where they are tasked to work with Phillip Clyde of Security and Strategy Corporation (SSC) to assassinate Abdullahi Mo'Alim. After this mission, Philip Clyde, on behalf of SSC CEO Ernest Stockwell, invites Lieutenant Colonel Richard Dalton (commander of the 75th Ranger Regiment) to join the company for a desk job. He agrees, asking to bring Salem and Rios with him as contractors, and, the following year, the three enter the private sector.
Salem and Rios begin an eight-year stretch of mercenary work in various U.S. operations until the events of September 11, 2001. They are then hired to infiltrate a mountain missile base (leftover by the Russians from the Cold War) in use by Al Qaeda. The are tasked with the destruction of medium-range M-11 missiles, the elimination of terrorist Al-Habiib, and the rescue of Brian Hicks(another SSC operative who was captured trying to accomplish the same tasks). After killing Al-Habiib, they destroy a cache of chemical warheads with the help of a hacker, working under the handle "Section Eight".
It is announced in the news that SSC has acquired Black Mountain Industries, another PMC. The merger makes SSC the largest PMC in the world, which causes controversy that they are becoming too powerful. Dalton reassures the public that their motives are pure.
In 2003, the two are sent back to Iraq by Alice Murray, their mission coordinator. Their mission is to rescue Lt. Col. Samuel Eisenhower, a friend from Salem and Rios' old Army Ranger squad. They are told he has vital information and is being held hostage in an American base which has fallen under enemy control. Salem and Rios successfully extract him to a helicopter. However, soon after it lifts off, it explodes. Salem comments that with Eisenhower dead, only he, Rios, Dalton, and another solider named Pedro are the only surviving members of their former ten-man unit. Ali Youssef, an Iraqi terrorist, claims responsibility for Eisenhower's death, and the two are tasked with eliminating him, his lieutenant, and his Iraqi base.
After the mission, Senators Alex Richter and Richard Whitehorse discuss a bill coming before Congress on TV. If passed, the bill would displace the military and replace it with private contractors, mostly from SSC. Whitehorse is opposed to the bill while Richter wants it to be passed, commenting that mercenaries have been outperforming soldiers.
While fighting enemies in the Philippines, the two are contacted and reassigned by Alice. The U.S. government recently sold the USS Constellation to Japan. It has been overtaken by terrorists from Abu Sayyaf, a powerful terror cell. The two are transported there via helicopter and parachute down to the flight deck. They are rejoined by Phillip Clyde, who they have not had to deal with since Somalia. Immediately after establishing contact with Salem and Rios, Clyde goes below deck, while Salem and Rios disable jets parked on the runways. Alice mentions that the Navy doesn't want SSC getting credit again, and so has dispatched a team to help. Eventually they go below deck hoping to find a way to the ship's bridge. Salem and Rios discover Clyde meeting with the terrorists. Clyde immediately escapes, leaving his laptop's USB Flash Drive on the table, which the two grab. It is then covertly sent to 'Section Eight' to be analyzed. After fighting their way onto the bridge, Navy Captain Harris of the USS Constellation informs them that the carrier has been turned into a nuclear bomb on a course to Manila, and the two must blow the ship up and sink it to the bottom of the ocean. On the way to handle the situation, they find the Navy team Alice informed them of dead, with Rios and Salem's former squadmate, Pedro, among the deceased. While maneuvering through the ship, 'Section Eight' has uncovered what was on Clyde's USB Flash Drive. The drive contained positions where ambushes to U.S. Army soldiers have taken place. This leads Salem and Rios to conclude that Clyde is working with the terrorists. They succeed in rigging the ship to explode, and narrowly escape while Harris goes down with his ship. After completing the mission, they decide to not take any other missions from SSC since they do not know who else is working with Clyde. They decide to wait until they go public with the information.
United States Senators, Alex Richter and Richard Whitehorse, continue their debate on the bill to privatize the military. Richter believes that doing so would be safer and cheaper than a standing military. However, Whitehorse doesn't want to pass responsibility to corporations who profit from war and may drag the U.S. into unnecessary conflicts. Whitehorse begins a campaign to see the bill is not passed.
Salem and Rios, now in South Korea, are doing a job for one of their weapons suppliers, Cha Min Soo. The two have remained out of contact with SSC as they try to investigate Clyde's involvement with the terrorists and a link between SSC and U.S. enemies. Salem's radio is accidentally switched on and Murray contacts them with one final mission, in China. The leader of Abu Sayyaf, the organization that orchestrated the capture of the Constellation, will be crossing the bridge over the Lijiang River. The two are to ambush his motorcade. After completing their assignment, Alice has lost sign of their extraction helicopter, and the two are dealing with Chinese military forces, not Abu Sayyaf. After some digging, Alice discovers that a bounty has been put out for the two, implicating their involvement with the murder of United States Senator Richard Whitehorse, who was in the motorcade they just blew up instead of the Abu Sayyaf leader. Along the way, the two tell Alice why they fell out of contact, letting her in on the potential conspiracy, which is furthered by the apparent setup. The three put the pieces together, guessing that Dalton and SSC CEO Stockwell set them up to kill Whitehorse, which would end his campaign against the bill and allow it to be passed. Rios and Salem were prime decoys, since they already knew about Clyde, who has been revealed by 'Section Eight' to have been involved in ambushes on U.S. Soldiers, staged to make the army look bad and further support for the bill. En route to escape from China, the two hear Alice being assaulted on the radio, presumably kidnapped. Having then escaped, they decided to end the fight.
Salem and Rios are then en route to Miami, where the headquarters of SSC is located. A hurricane is headed toward the coast of Florida, and the Air Force has sent two fighter jets to intercept their unauthorized flight into the United States, them having been given a plane by Cha Min Soo. Compounding their troubles, Philip Clyde is found stowed aboard their plane, having killed the flight crew. Salem and Rios fight Clyde while the Air Force shoots and damages the plane. They manage to get into the plane's on-board hovercraft as the plane is going down, but Clyde picks up a fallen FGM-148 Javelin missile launcher and fires, blowing off half of the plane. Their hovercraft manages to touch down in the waters of Miami, and they head to SSC island while Clyde is assumed dead in the crash. When Cha Min hears that his plane was crashed, he threatens to have Salem and Rios killed. They explain that Clyde was responsible, and Cha Min demands they kill him. Salem agrees, not letting Rios mention that Clyde has already been killed. The two are under increasing pressure from Cha Min as he hacks into their helmet cameras, watching them. The two are then contacted via radio by Ernest Stockwell, requesting that they get him out. He claims that he was not involved with the conspiracy but it was all the work of Richard Dalton, the boys' former military superior.
The two rescue the kidnapped Alice from the Miami Airport, where she tells them she has set away money from SSC in an offshore account for them. After she is escorted away, the two storm SSC HQ, where 'Section Eight' helps them get the elevator online so they can pursue Dalton. Along the way, Stockwell accepts a deal from the two to turn himself in, as Alice claimed he knew Dalton was breaking the rules, but not exactly what he was doing (sacrificing soldiers). Upstairs, the two are shocked to see Clyde has survived the crash, but thankful that they can now calm an enraged Cha Min, closing their debt with him and securing later favors. After an immense firefight on SSC's top floor, Salem and Rios throw Clyde out of a window, causing him to plummet into the flooded streets of Miami. Meanwhile, Dalton escapes to the roof, pursued by Rios and Salem. Although Dalton mans the turret of a helicopter, the two destroy it with an FIM-92 Stinger, sending Dalton to his death.
For the ending sequence, the game skips ahead several months. A news broadcast announces that Ernest Stockwell, CEO of the now defunct SSC, has been released from his six month prison sentence (having turned himself in as promised) halfway through. The "Privatization Scandal" is also mentioned; the bill having not been passed. Alice, watching the broadcast, receives a phone call from Rios, who tells them that he and Salem have started their own firm, Trans World Operations (TWO). When she asks how they got investors, the cameras pans to look at Cha Min Soo and Viktor Roshankov, their Ukranian body armor supplier. Rios mentions that they need a contract filer, and offers Alice the job. Alice smiles in agreement.