Having inherited Keith Wood's No.2 shirt, Byrne then preceded to make himself a fixture in the Irish team for the next three years.
And the highs achieved of a 2004 Triple Crown and being selected for the 2005 British & Irish Lions tour were all the more poignant considering Byrne came close to retiring in frustration.
He said: "I know it is a cliché but going on the Lions tour was beyond my wildest dreams.
"It was a wonderful experience full of huge highs and massive lows and was all the sweeter because I had nearly quit rugby in 1999.
"I first broke into the Irish squad in 1993 but despite being on the bench I don't know how many times, I never got onto the pitch.
"I was in competition with several people, notably Keith Wood, and I could go from being on the bench one week to sixth in line the next. I just did not see a way through.
"But my lowest ebb was when my old Under-19 coach Joe McDonald knocked some sense into me and in 2001 - after an eight-year wait - I finally got my first Ireland cap against Romania just a couple of months away from 30th birthday and just days away from my wedding,
"The game passed me by in a blur but it was incredible. We won the game 37-3 and once we returned to Ireland there was the enormous relief of actually having my first cap.
"But once that feeling wore off, I was hungry for more. My debut also got me out of organising my wedding which I was always grateful for."
Byrne will be remembered by Six Nations fans for two things primarily: the accuracy of his lineout throwing and his haircut.
And while Byrne is quick to pass the credit for his set-piece success to his jumpers, the now 39-year-old is quick to defend his distinctive barnet.
He said: "It was during the period I became a regular in the side that Ireland had the best lineout in the world.
"It has always traditionally been a strength of ours and I was lucky to have a strong relationship with Malcolm O'Kelly and then Paul O'Connell.
"In terms of my throwing, I only actually practiced with other people, I was never one of those hookers who spent hours throwing the ball at a post or something,
"The key to winning your lineout is not hitting your guy at the top of his jump but missing the opposition. I just put it in the air and they did the rest.
"I guess the other thing I will be remembered for is the Mullet. You can't have a hairstyle like mine and not expect a bit of a slagging.
"I would love to have some long-winded explanation for it but I just hate short hair.
"I have always been a rocker at heart and I have never seen the point in changing my style. I also came from a Gallic background so this was the person I was before I discovered rugby.
"Nearly every tour I went on I heard rumours that some of the lads were going to try and shave it. But ultimately I knew where they lived and there was never anyone brave enough to take it on."