Cole scored an amazing 68 goals in 83 games playing for Newcastle.
He left St James' Park in a contoversial move that took him to Old Trafford and Keith Gillespie arrived on Tyneside.
The Nottingham-born striker played a key part of the Manchester United side of the late 1990s, Cole's partnership with Dwight Yorke was a key feature in the 1999 Treble, while he won 15 international caps.
Toon Legend Hangs Up His Boots!
He also had spells with top-flight sides Arsenal, Blackburn, Fulham, and Manchester City.
He admits his acrimonious departure from Championship strugglers Nottingham Forest was not how he hoped to finish a staggering career.
Cole: "It's not the ideal ending.
"It just wasn't working out. I told them from the outset that I didn't want to go there to sit on the bench because I didn't want to be perceived as sitting back and making easy money.
"I wanted to go there and offer something, but it was a strange one from the start. I never knew what my role was. Was it to lend a hand, use my experience, or was it a PR thing, to sell a few more season tickets? I still don't know.
"I felt like the manager wouldn't have a conversation with me. I don't know if it's the right word, but he seemed kind of intimidated by me.
"People will look at it and say this is how they expected me to go, in a huff or in some kind of controversy, but it wasn't like that. I just wish Forest could have been honest. I've always been honest in my career, maybe too honest for my own good.
"I wouldn't change a thing. I've lived the dream."
Our funniest story of Andy was when he arrived at Newcastle and he was given a rented house in Crook, on the outskirts of Durham city (where they trained at that time). Very much a Mackem stronghold.
One Sunderland fan approached him in a pub in Crook, saying: "Hey, don't you play for Newcastle?
"If I give you a beer-mat and a pen, will you do me a favour?"
Andy took the pen ready to sign, then the Mackem said: "Will you get me Peter Beardsley's autograph!"