Anelka had previously gone ten Premiership matches without a goal until his spectacular first-half effort.
And he ensured Bolton's first victory in six games with an excellent second after a glorious pass from Ivan Campo.
But the Gunners, who haven't beaten Wanderers in the league at the Reebok since 1992, will feel they deserved at least a point.
They hit the woodwork three times in the second 45 minutes and carved out other good efforts.
But their remote title hopes took another dent with this defeat as Bolton climbed back to third.
It could have been different had Kevin Davies been sent off for a push on Emmanuel Eboue.
However, he and Bolton survived to make it a happy day for the Lancastrians.
Thierry Henry's absence enabled Theo Walcott to start a Premiership game for only the second time.
Bolton welcomed back proud new dad Kevin Nolan, brought Abdoulaye Faye into midfield and relegated Idan Tal and Campo to the bench.
Walcott was soon in the thick of the action and a teasing cross after just 90 seconds allowed Emmanuel Adebayor to test Jussi Jaaskelainen from close range.
Walcott then played in Eboue whose cross was almost turned into his own goal by Nicky Hunt.
It was against the run of play when Wanderers took an eighth minute lead. From their second corner of the game, El Hadji Diouf curled in a cross, Kolo Toure lost his marker and Faye powered home a close-range header.
An Arsenal break down the Bolton right ended with Abdoulaye Meite and Gary Speed clearing crosses at their near post with the balls heading for the bottom corner.
Then came the flashpoint. Davies clearly caught Eboue with a late tackle though it certainly wasn't a leg breaker.
The Ivory Coast international immediately confronted the Wanderers striker who pushed his opponent in the chest.
Eboue crashed to the ground and both Davies and referee Mike Dean were surrounded by Gunners players.
Just what the incident had to do with Jens Lehmann who was 30 yards away only he knows.The outcome was customary Arsene Wenger apoplexy and a yellow card for Davies.
The card was brandished again soon afterwards to Freddie Ljungberg and
not surprisingly Lehmann for dissent.
And from one incident Arsenal's habitual fears about travelling to the Reebok manifested themselves again.
But Bolton were in trouble before the break when Quinton Fortune and Hunt went down injured at the same time. They were then forced to defend the corner with only nine men.
Jinxed Fortune was unable to continue while Hunt hobbled on until the break.
With four minutes of stoppage time both sides scored. Anelka collected Davies' hopeful cross-field pass and then cut in from the left wing before unleashing a brilliant strike beyond Lehmann.
However, Bolton were still re-organising when Gilberto Silva headed in a Cesc Fabregas cross to give Arsenal hope. Nolan later admitted his marking had been as poor as Toure's earlier.
It might even have been 2-2 but Ljungberg couldn't quite connect six yards out.
And Arsenal certainly should have been on level terms early in the second half. Jaaskelainen made a great save to keep out a 20-yarder from Fabregas while Freddie Ljungberg headed against a post from Walcott's cross after the teenager left Faye stranded.
It seemed the Londoners must equalise. Instead, Bolton broke away, Campo, playing at right back, threaded through a great pass and Anelka finished the outcome.
There was still time for Arsenal to hit the bar but their Reebok curse struck again.