At the time, he had little idea that a British-record deal would have implications for him, a free agent nearing the end of his career.

It was February 2011, and Kuqi was looking for a new club after leaving Swansea City. Aged 34 at the time, the striker knew his playing career was winding to a close, but he was not ready to hang up his boots. Little did he know, as he waited for a call, that one of his biggest footballing challenges was yet to come.

Newcastle United fans, meanwhile, were coming to terms with the £35m sale of Andy Carroll to Liverpool. Carroll had left the club on deadline day, and there had been no time to sign a replacement before the transfer window closed.

So, as Kuqi considered his next move in South Wales, then-United manager Alan Pardew and his staff were sifting through a list of free agents in North East England. The name of Kuqi, a player Pardew had long admired, was on that list, and so one of the unlikelier transfers of the Premier League era came to pass.

It was early evening when Kuqi got the call from Pardew in Swansea, where he was still living. "I was a free agent, because I had terminated my contract," said Kuqi, who also spent three years with Sunday's opposition, Crystal Palace.

"It happened pretty quickly. Alan Pardew, the manager, knew me pretty well. I'd played a few times against his teams. That's when the call came, and it was really nice.

"It was in the evening, and the manager said 'I want you to be here tomorrow morning', so it was an early start, because I was in Swansea. I left quite early to get there in time."

His debut came quickly too. Two days later, Kuqi was cheered off the bench away to Blackburn Rovers, one of his former clubs, by United’s 5,000-strong support in the 89th minute at Ewood Park. It was a memorable moment for a journeyman player who had not envisaged a Premier League swansong.

"It was special, and honestly I mean this," Kuqi told newcastleunited.com. "You have to actually be there to get the feeling about the support they have, and the whole club. Before you spend some time there, you can only see and imagine. But to be there and experience it is something special.

"What I liked about the club and the support is that they accept things - as long as you give everything.

"If you work hard, the result, whatever it is, they accept that. That's a privilege. Supporters understand that players are human beings, and sometimes you have a bad day.

"It was an honour, and special, to spend some time there."

Kuqi's stay on Tyneside, ultimately, was a short one, but his story is a long one. It started in Kosovo, then part of former Yugoslavia, and today its latest chapter finds him managing a club on a Mediterranean island.

As a young boy, Kuqi and his family had fled their home in Vushtrri amid rising ethnic tensions in the country. They headed to Belgrade by train, and then found their way, over land and sea, to Finland, where they arrived as refugees. Kuqi had left everything he had known behind for reasons he, at the time, did not fully understand.

"Moving from Kosovo, I was a really young boy, like 11 or 12 years old," said Kuqi, now 49. "When that move comes, you don't understand why. You leave everybody - family, friends, school. You leave everything to go to a country you haven't heard of before. You start a new life, and think 'where do we go from here?'." It was "tough" at first, but Kuqi's footballing talent was soon recognised.

"I have always said the biggest challenge for anybody if you're going to have success is going to be yourself," said Kuqi. "How much do you really want something? Day by day, you take the challenge and you just move forward.

"I remember I had tough times in the beginning when I started playing in Finland, because they were not accepting me as a player, because I was foreign. That was hard to understand, and harsh.

"But that all changed. When I moved, it was 1989. Today it's so different. They don't see where you're from, they see you as a normal human being. At that time, it was quite different.

"I had a good time in Finland. It was tough in the beginning. I think it was always that passion and love of football that got me through. In the first couple of years, I never even got paid anything.

"We got residency, and moved 50 kilometres away. I had to travel there and back (to my club), and it got to the stage where I had to get paid something, or we wouldn't have had money to travel.

"I was scared to ask the club 'can you pay me the expenses?'. Let alone asking for a salary. Those times make you stronger.

"Everything started from there. I started playing at a higher level, and managed to go to the top level in Finland. I was in HJK (Helsinki) when we won the league, and were the only team in Finnish history to qualify for the Champions League group stage.

"I remember that was something special. When we played the first Champions League games, it was like 'wow'."

Kuqi's first club in England was Stockport County, and his success there earned him a move to Sheffield Wednesday. Nine years later, the call would come from Pardew. However, United fans might have seen Kuqi during his peak years. Kuqi had led the line for HJK Helsinki against Sir Bobby Robson's PSV Eindhoven in two Champions League group-stage fixtures in the late 1990s.

And Sir Bobby, appointed United manager in 1999, considered signing Kuqi when he was at Ipswich Town a few years later. "I had a close friend of Sir Bobby Robson, one of the Ipswich guys," said Kuqi. "They were friends with him, and they told me, at one stage, he was really keen to bring me to Newcastle."

Had Kuqi joined the club in his 20s during Sir Bobby's time in charge, he may well have had a longer stay at St. James' Park. "Absolutely, I think that would have been a different outcome," said Kuqi. As it was, Kuqi played just 23 minutes of football, spread over six appearances from the bench.

"It was a great feeling, because to play for that club is a big honour," said Kuqi, who won 62 caps for Finland during an 11-year international career.

Kuqi's transfer had come about because of Carroll's sale, but he had not been fazed by the unexpected move. "You always feel the pressure, and want to do well, especially for a club that size," said Kuqi. "But I felt like 'I'm going to go there and do my best. Let's see where we go from here'.

"You can only be yourself. For me, to try and be somebody which I'm not, I don't think it’s fair. You always want to do well. I wanted to spend more time at that club, and to do that I had to do pretty well, but I didn't get a lot of opportunities."

Kuqi had idolised Alan Shearer, the club's all-time record goalscorer, as a young footballer.

"I loved Shearer," he said. "He was a player who guaranteed you over 20 goals every season. His style of play too. He could score from anywhere - headers, long range, tap-ins.

"He was an all-round player. I always said the goals I enjoyed most were tap-ins, like half a yard from the line. For me, that's about smelling the situation, and being in the right place.

"Outside the box, you score every couple of years, but Shearer had that in his locker. He could put it in the top corner from 30, 40 yards."

Kuqi returned to St. James' Park with his daughter a couple of years after leaving the club for a derby match against Sunderland, and he experienced a red-hot atmosphere on a chilly day.

"We were almost behind the goal," said Kuqi. "It was great to experience that. As a player, your focus is on the game. Your only focus is on the pitch. You can hear the noise, but that's it. You don't experience watching a game from the side.

"I decided to go there for the Sunderland game, and it was quite a game. Unfortunately, we lost that time.

"I remember the atmosphere and the passion. It was quite cold, but the guys were in their t-shirts. You could see that their blood was boiling! It was some experience."

Kuqi had had an up-and-down spell at Palace under Neil Warnock earlier in his career.

"Like all strikers, when you get your chance, a few games running, you can get a decent amount of goals," said Kuqi. "You need that little bit of luck, and it also depends on the team, and how your style of play suits the team."

Kuqi still follows the fortunes of United. He said: "Thankfully, they are moving forward. It's always nice to see your former clubs doing well."

Kuqi, manager of Chania in Crete, now has the "challenge" of building a team. "I’m enjoying it," he said. "It's difficult, totally different to being a player, like day and night! But I enjoy it. I've been lucky enough to play for so many clubs under different managers. I've taken loads of different things (from all of them).

"One thing is for sure, you have to be yourself. If you just try to copy somebody, you're going to be nobody. It's quite enjoyable for me.

"I always loved a challenge, and being a manager is quite a challenge!"

Kuqi's life and career has been full of challenges. "It's quite a journey," he said, making something of an understatement.

One thing still "hurts" Kuqi, though, when he looks back at his playing career.

"When I look back now on my career, everywhere I have been I managed to score goals, but Newcastle I didn't get that opportunity," said Kuqi. "I didn't manage to score. That still hurts me."

A Kuqi goal at St. James' Park, followed by his trademark leap and swallow dive celebration, would have been a sight to behold. But Kuqi still made a big impression during his brief spell at St. James' Park.