But the Bolton scout had received an important tip from someone who knew the French striker far better than most, and he was convinced the player was ready to turn his career around.
It would take some persuading. Sam Allardyce had heard the warnings, other managers were advising against the move and Anelka was playing in Turkey with Fenerbahçe.
Worthington, however, believed he had discovered something that others had missed. The striker had matured, his personal circumstances had changed and, crucially, he still possessed the ability to score 20 goals a season.
The Bolton scout was prepared to put his reputation on the line to make the signing happen. It would prove one of the most rewarding pieces of recruitment of his career, and a story that would eventually follow him from Bolton to Chelsea.
The Paris connection that changed Anelka's career
"With Nic, a lot of people didn't want him. He'd been in England, he'd been in the Premier League, he'd messed up a little bit with his brother.
"I think his brother was pushing him a bit too far at times as his agent. You know, saying, do things for the family. You've got to help the family and all this.
"But I got a message from a youth agent. I knew the boy. He was from Paris, and he rang me one day. His name is Salem Kassa.
"Salem said to me, 'Dave, you know, Nic's not very happy over in Fenerbahçe, and he's wanting to come back to England.'
"I said, 'I don't think the manager would like him. He's been a bit moody and a bit off in his playing in the Premier League.'
"And he said, 'Let me tell you this. I grew up with him in the streets of Paris. I grew up with him as a young kid. He had a tough upbringing.'
"He said he was pushed about by his agent at the time and he was moving from club to club. Manchester City, Liverpool. He just told me the story," Worthington told Football Presse.
Kassa's message was that Anelka was no longer the same character who had developed a reputation for being difficult to manage.
He had met Barbara, a dancer and choreographer, fallen in love and was preparing for marriage. His relationship with his former agent had also ended, while Worthington was told that Anelka was changing religion.
It was a different picture from the one that had followed the striker through his previous spells in England.
"He's grown up. He's met Barbara, who's a dancer and a choreographer, and he seems to have fallen in love.
"He's changing religion, and he's not got the same agent anymore.
"And he says, you know, do you think that Bolton might be able to buy him?"
Worthington knew the financial side would be important, but he immediately saw an opportunity. Anelka was available for around £7-8 million, and Bolton needed a striker capable of delivering goals at the highest level.
The challenge was persuading Allardyce to overlook the reputation and concentrate on the player he could become.
Allardyce's doubts, the warnings and a secret trip to Turkey
Worthington's recommendation was not universally welcomed. Indeed, some of Allardyce's fellow managers were strongly against the idea.
"I told the gaffer this, and a lot of Sam's manager mates, Bryan Robson and people like that, they all said, 'Don't take him. No, he's never going to be any good. He won't change his attitude.'
"But I kept saying, 'Gaffer, he's changed. We've got to forget that bit. We need a striker who can score 20 goals a season. I say he can do that. He's got all the class in the world.'
"He said, 'Well, look, stop moaning. Get on a plane. You get out and watch him a couple of times. Go watch him at Fenerbahçe. You don't let anybody know you're going. Just get out there and go watch him.'"
It was exactly what Worthington wanted to do. He travelled to Turkey and watched Anelka on several occasions, looking beyond the previous criticism to assess his attitude and application.
What he saw reinforced everything Kassa had told him.
"I watched him a couple of times and his attitude was spot-on. I thought this is far different to what other people saw in him, because his attitude had changed.
"I think he was wanting to get married, and it was good then because I was one of the first, because I'd got the heads-up from this agent."
Having watched Anelka in Turkey and become convinced that his attitude had changed, Worthington and Allardyce still had to persuade the striker that Bolton was the right destination.
They arranged a discreet meeting in Paris, with both travelling to Charles de Gaulle airport to sit down with the Frenchman. Worthington remembers the preparations, including a presentation designed to show Anelka what life could look like in the north-west of England.
"It was a strange one as well because we had to do a sneaky one.
"I flew out from somewhere, Sam flew back from Germany. I think he was doing some commentating during one of the tournaments, and we flew to Charles de Gaulle airport in Paris and met Nic.
"We met Nic there. And the main thing I liked about Nic that day was we sat in a meeting with him and he listened to every word that Sam said. He stared at Sam in the eyes and listened to him.
"We put everything together about where he could live. The IT boys put a video film together of various things, the best things about Bolton and Manchester, and where he might be able to live in Cheshire and what he might be able to do there.
"We did a good job, but the main thing was Nic never took his eyes off Sam when Sam was speaking. He was just staring at him and listening to him."
For Worthington, that concentration was telling. He had already seen the change in Anelka's attitude on the pitch in Turkey. Now he was seeing a player who was genuinely listening to what Allardyce had to offer.
The manager, however, was less certain about how the meeting had gone.
"Afterwards Sam said, 'I'm not sure where we're going with this one.' He said, 'What do you think?'
"I said, 'He listened to every single word you said, so I bet you we're getting him.'
"And sure enough, during that summer, we signed him for seven, eight million.
"Sam rang me up a couple of days later and said he's signing. He started, so it was brilliant. Absolutely brilliant.
"It was a really satisfying one.
Bolton had taken a chance on a player many others were reluctant to touch. Worthington's judgement was about to be vindicated.
The Frenchman settled into life at the club, remained relatively quiet away from the pitch and concentrated on his football.
"What a breath of fresh air he was. He was quiet, yes, a quiet Muslim boy, but he just got on with his job when he scored goals for us.
"I think he got 21 goals that year. It was fantastic."
Anelka had become precisely the striker Worthington had promised Allardyce he could be. But the scout also discovered another side to the Frenchman, one that would leave a lasting impression on the Bolton staff.
The Marrakech wedding that showed another side of Anelka
Anelka was preparing to marry Barbara, and after enjoying such a successful spell at Bolton, he wanted to share the celebrations with the people who had helped him during his time at the club.
It was not an invitation reserved for the playing staff or senior coaching personnel. Anelka offered the opportunity to anybody working at Bolton, paying for three days at a five-star hotel in Marrakech and arranging activities for the guests.
"He was getting married that year and because he'd done so well at Bolton, during the summer when he got married, he offered the chance for anybody on the staff at Bolton, not just coaching staff, to go out.
"He was having three days of celebrations in Marrakech, and he offered a five-star hotel for three days. Anybody who wanted to go, put your name down on the list. 'I'll pay for it all.'
"He put things on in Marrakech as well during the day for us. Not only paying for all the hospitality, but coach rides into Marrakech centre and things, on the horse and carriage.
"He was brilliant."
Worthington remembers that some of his friends were rather more cynical about the gesture when he returned. Anelka was a wealthy footballer, after all, and could easily afford to pay for a few days away.
But that missed the point, according to the scout.
"A lot of my cynical friends when I came back said, 'Well, he's got all that money. He can afford to do it.'
"I said he didn't need to say that to the Bolton people. He didn't need to say that to us all. He went out and spent his money.
"So I've always got a lot of respect for Nick in that."
For Worthington, it was another indication of how wrong the assumptions about Anelka had been. The quiet, focused forward who had arrived at Bolton had also shown generosity towards people who were not necessarily in a position to do anything for him.
And when Worthington subsequently moved from Bolton to Chelsea, he was not prepared to let the club forget what he had learned about the Frenchman.
The Chelsea battle: I kept putting Anelka's name forward every month
Worthington's move to Stamford Bridge presented an opportunity to continue backing a player he knew intimately. He had watched Anelka transform his career at Bolton, seen the attitude that had impressed him in Turkey and witnessed the goals that followed.
He also knew that other scouts and recruitment staff might still be judging the striker on his earlier reputation.
So he kept making the recommendation.
At Chelsea, sporting director Frank Arnesen requested regular reports from the scouting department, with lists of potential players submitted every month for the various positions.
Worthington had no difficulty identifying the name he wanted on those lists.
"I continued to tell Chelsea to sign him. Eventually, but it was me that started that off because I knew this new attitude in him.
"I know that other scouts and other chief scouts at other clubs didn't know that."
But Arnesen was not convinced. Month after month, Anelka's name kept appearing, until the Chelsea executive finally wanted to know why Worthington was so determined to recommend a player the club apparently had no intention of signing.
"Frank Arnesen requested every month that we put a list of players in, so there'd be a list of every position.
"And for every month I kept putting in Nicolas Anelka, Nicolas Anelka, Nicolas Anelka.
"And Frank said to me, 'Dave, why do you keep doing that? You know we're not going to sign him.'
"And I said, 'Well, you should do.'
"And I kept telling him the story, 'He's changed, he's changed.'"
There is a lovely sense of persistence in Worthington's recollection. He was not prepared to accept that the player's past should determine his future, particularly when he had first-hand knowledge of the transformation.
He had been the one who had pushed for Bolton to take the risk, had watched Anelka deliver the goals and had seen the personal side of the player that others might never have encountered.
Now he was making exactly the same argument at one of the biggest clubs in Europe.
Eventually, Arnesen relented.
"And eventually I must have worn him down because he did sign him."
For Worthington, the outcome was particularly satisfying. Bolton had bought Anelka for around £7-8 million, sold him to Chelsea for approximately £15 million and, in doing so, doubled their investment.
But the transfer also provided something more personal: vindication of a judgement he had been making long before Chelsea became interested.
"Then he went on to score 20 goals for Chelsea, so I love that man.
"In my view, that is the best I could have done really, you know.
"Full marks to me."
Anelka finished as the Premier League's leading scorer in 2008-09, with 19 league goals, winning the Golden Boot in his first full season at Stamford Bridge. He also scored 25 times in all competitions.
It was another outstanding return from a player Worthington had refused to give up on.
From the initial conversation with Salem Kassa to persuading Allardyce to take a chance, and then repeatedly putting Anelka's name in front of Arnesen at Chelsea, Worthington had played an important part in a remarkable chapter of the Frenchman's career.
The most satisfying part might have been the simple fact that he had been right all along. Others had remembered the reputation. Worthington had seen the person and the footballer who had emerged from it.
Dave Worthington is author of "Worthy: The Scouting Adventures and Football Life of Dave Worthington" - which is available here.
