"I had lost a girl friend for not being a good looking man who would make it to the movies, but I got the job because I wasn't good looking," Shah said.
The 65-year-old actor was in conversation with writer and actor Girish Karnad at the "And Then One Day" session on the opening day of the Jaipur Literature Festival.
Interestingly, there is a long history behind the camaraderie between the two.
Karnad was the director of prestigious Film and Television Institute of India when Nasser was a student there and it was he who had suggested Shah's name to Benegal, who was sure that he didn't want a "conventional chocolaty boy" for the role.
"Once Naseer had come to me and asked if him being a Muslim would be an obstacle to his acting career? I had told him that Dilip Kumar too was a Muslim who was loved by many and all," said Karnad.
But even after making a powerful debut, Shah recollected how "instant fame" was difficult to come by and how he had to go through a period of struggle when he was relatively "jobless".
However, Benegal's "Manthan", which also featured Karnad, changed the course of his career and Shah was seen in a slew of films like "Sparsh" "Aakrosh" and "Mandi" that required a method actor and not a star.
Yet, the lament of not-being a star has disappointed Shah, who admitted that he hadn't joined the industry to do "art movies", but slowly came in terms with his ordinary looks.
"I never became a star and I have to admit that it was disappointing," said Shah.
"But then I started examining my face and realised I could alter it. Even from my early years, when I was 15 or 16, I had this habit of growing beard and my greatest achievement was when my mother couldn't recognise me," he added.
Even if the seasoned actor thought he wasn't a star, the reception he received from the crowd was overwhelming as they shouted and clapped at his arrival on the stage.
This response reconfirmed how people loved him for his acting and ordinary looks that have become unconventional in their own way.