In October 2001, when Strachan assumed managerial duties at Southampton, he brought Telfer along on a free transfer. This move marked a positional shift—Telfer transitioned from midfield to right-back. Over four seasons in the Premier League, he made 127 league appearances and scored once, contributing significantly to Southampton's 2003 FA Cup Final run. In 2005, Strachan, now manager at Celtic, again recruited Telfer—this time for £200,000. The defender enjoyed two productive seasons at Celtic Park, amassing 57 league appearances, scoring once, and helping secure two Scottish Premier League titles before retiring in December 2006 at age 35 due to family considerations.

Telfer briefly came out of retirement in July 2007, signing a one-year deal with League One Bournemouth. He featured 18 times before a foot injury in December forced him out of action. Shortly before Christmas, Telfer asked manager Kevin Bond and the club's board to cancel his deal and allow him to address a chronic foot injury. Telfer offered to forego the remainder of the salary he was owed, a gesture which Bournemouth accepted gratefully as the claws of administration closed in on Dean Court. Bond was amazed by the charitable suggestion, and shook Telfer's hand gratefully.

'I've never seen a player do that in all my time in football,' said Bond. 'I don't care how rich footballers are or how much money they've earned - it doesn't happen. Paul was the exception to that rule, and his gesture was unbelievable.' It was widely assumed that Telfer's career had run its course, but Bond knew he had merely reached the end of his time with Bournemouth. With a successful operation on his foot behind him, the close season brought with it a fresh start, handed to him by former Coventry City team-mate Gary McAllister, then managing League One Leeds United.

UInitially training on a non-contractual basis to maintain fitness, Telfer joined Leeds on a pre-season tour of Ireland but formally signed a one-year deal at the end of August. While his career had mostly been at right-back, his debut appearance—in a League Cup-tie against Crystal Palace—saw him deployed centrally, where he impressed with assured defending.

Between that debut and early 2009, Telfer made 14 league appearances and featured twice in the FA Cup and twice in League Cup fixtures. His 18 total appearances represented a late-career revival, showcasing his adaptability and commitment. In November 2008, he notably featured in Leeds’ 2–1 loss to Huddersfield, where a misplaced pass led to a late goal—an incident that supporters flagged as illustrating his reduced pace. Despite this lapse, he put in solid defensive performances in numerous matches, displaying the experience and professionalism that had carried him through decades at the top levels of British football.

However, a managerial shake-up in December 2008 brought Simon Grayson into the manager's office. Grayson pursued younger centre-backs during his first window, such as Richard Naylor. Consequently, Telfer was omitted from all first-team squads under the new regime. A conversation between player and manager led to a mutual termination of his contract on 2 February 2009, amid concern that Leeds shouldn’t incur wage costs for an unused squad member.

Telfer said, 'It's strange because Simon's in the same position that Gary McAllister was in when he first came to Leeds. The club have got far too many players on their books and it's something Simon's trying to address. It's not always a healthy situation when you've got big groups of guys who are training with a club but aren't going to play, and I thought it was best if I helped him with that.

'I wasn't in the team and I accepted that because the defence improved under him with other players in it, so I went to see him and said that I thought it would be better for him if I wasn't hanging around the place. He assured me that I wasn't in the way or causing a nuisance but he was very honest about the fact that I might not get a game there. It was all very amicable and we decided it was best to go our separate ways. I think it was important for Leeds that I took that decision.

Though his spell was short-lived, Telfer arrived at Leeds in a period of instability. Often deployed at centre-back, a position somewhat foreign to him, he nonetheless adapted and secured regular starts until squad restructuring under Grayson. His departure underscored both his selflessness and professionalism—understanding his role had diminished and respectfully stepping aside for the team’s benefit.

Following his Leeds exit, Telfer signed for non-league Slough Town in April 2009, reuniting with his former teammate Darren Salton (assistant manager). He managed just one appearance before retiring permanently. In 2011, Telfer embraced a player-coach role with Sutton United, where he provided on-field experience and initiated his transition into coaching.

Reflecting on his contribution to Leeds, Telfer represented experienced cover during a transitional era. Signed by McAllister, his adaptability brought defensive depth amid managerial and tactical fluidity. Though his pace was criticised and a single error drew attention, he offered leadership and stability during a crucial promotion campaign that ultimately saw Leeds secure a play-off spot.

Throughout his career, Telfer was celebrated for his aerial strength, positional sense, and footballing intelligence—traits vital in his five-year Premier League tenure with Southampton, his spell in Scotland’s top flight with Celtic, and his late-career comeback in League One . His longevity reflects a player who learned from every phase—midfield dynamism in his youth, defensive solidity in top leagues, and judicious adaptation in veteran years.

Internationally, while capped just once by Scotland in 2000, Telfer also earned caps at Scotland U21 and B levels, reinforcing his status as a trusted and respected figure throughout his playing days.

Summing up, Paul Telfer’s career stands as a model of adaptability, professionalism, and resilience. From his early days as a midfield stalwart at Luton, through years of Premier League battles, Cup finals, and Scottish titles, to late-career service in the lower leagues, he displayed an unwavering love for football and an ever-ready readiness to contribute. His affiliation with Leeds United, though brief, encapsulated those qualities—arriving in need, performing when required, and departing with grace.

As of 2025, Telfer has continued his football journey off the pitch—coaching, mentoring, and passing on the experience of a career that navigated diverse football cultures, positions, and projects. His Leeds chapter may have been fleeting, but it exemplified the journey of a consummate professional whose dedication and class transcend mere statistics, leaving an understated yet meaningful legacy across multiple levels of the game.