At a bistro in the Montmartre district of Paris, IRA operative Deirdre (Natascha McElhone) meets with ex-special operatives-turned mercenaries Sam (Robert De Niro) and Larry (Skipp Sudduth), both Americans, and Vincent (Jean Reno), a Frenchman. She takes them to a warehouse where fellow mercenaries, German Gregor (Stellan Skarsgård) and English Spence (Sean Bean), are waiting. There, Deirdre briefs the men on their mission: they have been hired to attack a heavily armed convoy and steal a large metallic briefcase, the contents of which are never revealed. As the team prepares, Deirdre meets with her ex-IRA handler, Seamus O'Rourke (Jonathan Pryce), who reveals that the Russian mob is bidding for the case and the team must intervene. After Spence is exposed as a fraud by Sam and summarily dismissed, the others depart for Nice. Sam and Deirdre develop an attraction to each other during a stakeout. On the day of the sale, Deirdre's team ambush the convoy at La Turbie and pursue the survivors back to Nice. After a gun battle at the port, Gregor steals the case and disappears.
Gregor tries to sell the case to the Russians, but he is forced to kill his contact when he betrays him. He then contacts Mikhi (Féodor Atkine), the Russian mobster in charge of the deal, and makes him agree to another meeting. The rest of the team later track Gregor through one of Sam's old CIA contacts and corner him in the Arles Amphitheatre, where he is meeting two of Mikhi's men. Gregor flees but is captured by Seamus, who kills Larry and escapes with Deirdre. Sam gets shot saving Vincent's life and is taken to a villa in Les Baux-de-Provence owned by Vincent's friend Jean-Pierre (Michael Lonsdale). After removing the bullet and letting Sam recuperate, Vincent asks Jean-Pierre to help them locate Gregor and the Irish.
Back in Paris, Gregor is brutally interrogated into leading Seamus and Deirdre to a post office, where they retrieve the case. Sam and Vincent pursue them in a high-speed chase, which ends when Vincent shoots out Deirdre's tires and sends her car over a highway overpass. Gregor flees with the case while roadworkers save Deirdre and Seamus from the burning vehicle. Sam and Vincent then decide to track down the Russians and learn from one of Jean-Pierre's contacts that they are involved with figure skater Natacha Kirilova (Katarina Witt), who is appearing at Le Zénith arena.
That night during her performance, Natacha's boyfriend Mikhi meets with Gregor, who reveals there is a sniper in the arena who will shoot Natacha if Mikhi betrays him again. Mikhi kills Gregor anyway and leaves with the case, letting the sniper kill Natacha. Sam and Vincent follow the panicked mob out of the arena in time to see Seamus shoot Mikhi and steal back the case. Sam runs ahead and finds Deirdre waiting in the getaway car; he urges her to leave, revealing himself to be an active CIA agent pursuing Seamus, not the case. Deirdre drives away, forcing Seamus to run back to the arena with Sam in pursuit. In the final showdown, Seamus is about to kill Sam when he is fatally shot by Vincent.
Sometime later, in the bistro where they first met, Sam and Vincent talk while a radio broadcast announces that a peace agreement was reached between Sinn Féin and the British government, partly as a result of Seamus' death. Sam looks toward the door expectantly, but Vincent reminds him that Deirdre will not be coming back. After parting, Sam drives off with his CIA contact. Vincent pays the bill and leaves.

Question: Who shoots Natacha?
Answer: Seamus