Tottenham were his dream club. The former England international had already turned down Arsenal and was considering the prospect of joining Spurs after establishing himself at Queens Park Rangers. Venables, who had managed Tottenham to FA Cup success earlier that year before becoming the club's chief executive following Alan Sugar's takeover, was central to the discussions.
Yet when Manchester United entered the picture, it was Venables who encouraged Parker to consider the move, even though it meant Tottenham potentially losing out on a player he wanted to bring to White Hart Lane.
"Well, Arsenal was the first club I talked to," Parker told Football Presse. "And as you know already, that fell out of bed over the fact of there was no great benefit at that given time for me to go to Arsenal. I just didn't see a great benefit in me going there, and it wasn't somewhere that grabbed me. In my head, it didn't really grab me at the time.
"Rangers were one of the best sides in London, and I just had this love affair with Queens Park Rangers. I wasn't overimpressed with the manager at that given time, but I still had something QPR in my heart."
Parker had spent four years at Loftus Road, becoming one of the country's outstanding defenders and establishing himself in the England side. Following his performances at the 1990 World Cup, his reputation had grown considerably, attracting interest from several clubs.
Tottenham offered the possibility of fulfilling a childhood ambition without leaving London. Parker was comfortable with his surroundings, his friends and the familiarity of the capital. Then Maurice Watkins, Manchester United's solicitor and a key figure in the club's transfer dealings under Sir Alex Ferguson, contacted Parker's agent.
The call came while Parker was with Venables at the Royal Lancaster Hotel, overlooking Hyde Park.
"But I was with Terry Venables in the Royal Lancaster Hotel, Hyde Park. Sitting there with him and I thought, well, it looks like I'll be staying in London. I ain't got to move, haven't really got to move out the area where I'm in, which I still live in now.
"And just chatting away and everything, just sitting there, and it was just, everything was just brilliant, you know."
Then Watkins made his approach.
"And then Maurice Watkins, the late Maurice Watkins, the club solicitor, rang up my agent and said, would I be willing? And Terry Venables heard that, you know, he heard, he knew what's happened. And he just virtually said, 'You've got to go out of respect. If you don't go, you could regret it.'
"And my whole thing was kind of, should I, shouldn't I? You know, was he being too nice? And if I go, could I come back? And then him seeing me as somebody who didn't really want to go there (to Tottenham), had to go there. But he just said, 'You've got to go.' He said, you know, 'You've got to go and do it.' And I knew I had to do it."
There was something particularly significant about Venables' advice. Having been Tottenham's manager since 1987, he had returned the club to the FA Cup summit in 1991 and was now its chief executive. He knew what Parker could bring to Spurs, but he also recognised the significance of Manchester United's interest.
For Parker, the prospect of moving north was not particularly appealing. His football career had been built in London, and he had little desire to leave the people and places he knew. But this was Manchester United, a club whose history and stature made the decision different from any other opportunity.
"I knew I loved where I live. I love London. All my football's been in London. I could lose what I've got, you know, if I went north, but because it was Manchester United, I had to go."
Discovering a different world at Old Trafford
Parker's first impressions of United helped confirm that he had made the right decision. He had played at Old Trafford as an opposition player, but arriving at the stadium without a match taking place revealed something he had never experienced at QPR.
Cars were parked on the concourse, with people visiting the club shop and museum. The sheer scale of the operation surprised him.
"And then once I got there, just seeing what the ground was like without a game, you know, it was like Queens Park Rangers on a match day there. All the cars parked on the concourse, which obviously doesn't happen now, but that's where all these people used to park their cars to go in the club shop and the museum.
"I mean, I only found out about a museum, you know, about an hour after I arrived, asking what all those people are doing walking around the ground and, 'Oh, we've got a museum.' You've got a what?
"You know, their club shop was maybe as big as one side of Queens Park Rangers' ground. It was just completely different. It was football, and my whole thing was always to go and chase and be at the top."
Parker also arrived at a club with a different recent history to the one that would subsequently dominate English football. Ferguson had already delivered the FA Cup in 1990 and the European Cup Winners' Cup in 1991, but United had not won the league title since 1967.
Parker insists that winning the championship was not what initially attracted him. It was the opportunity to represent one of football's most recognisable institutions.
"Did I go there thinking, oh, it's all about winning the league? It never crossed my mind about winning the league. It was just the fact it was Manchester United.
"My dad from Jamaica, George Best, Denis Law, Bobby Charlton. They were the three football things he knew."
Leaving London meant sacrificing his familiar social life, but Parker believed his ambition had to take priority.
"Was I gonna miss all my mates, my social life and everything in London? Yes, I was. But I was just one of those people, I can go anywhere, sit somewhere on my own and be in my own company and just do it.
"And I just saw that that was the opportunity. I had to go and grab it."
Venables had told him he might regret turning United down. Parker chose to listen, leaving Tottenham's dream signing to become a Manchester United player.
It proved a decision that would bring two league titles, an FA Cup and a League Cup, but the opportunity itself was what mattered most.
Looking back, Parker has little doubt about the importance of that afternoon in London.
Paul Parker's book "Tackling the Game: My Life in Football" is from Pitch Publishing - which is available here.
