"So why would I give up the coveted green card for temporary status?" Mr Nadella writes in his book 'Hit Refresh', which officially releases in the US on Tuesday.
He married Anu in 1993. Following the wedding, Mr Nadella intended to bring his wife over to the US to live with him.
"Well, the H-1B enables spouses to come to the US while their husbands and wives are working here. Such is the perverse logic of this immigration law. There was nothing I could do about it. Anu was my priority. And that made my decision a simple one," Mr Nadella explains in his book.
Mr Nadella says he went back to the US embassy in Delhi in June of 1994 and told a clerk that he wanted to give back his green card and apply for an H-1B visa. "'Why?' the dumbfounded clerk asked. I said something about the crazy immigration policy and he shook his head and pushed a new form to me," Mr Nadella writes.
"The next morning, I returned to apply for a H-1B application. Miraculously, it all worked. Anu joined me (for good) in Seattle, where we would start a family and build a life together," he says.
"What I didn't expect was the instant notoriety around campus," writes Mr Nadella. "'Hey, there goes the guy who gave up his green card.'"
He says every other day someone would call him and ask for advice.
Mr Nadella says that much later, one of his colleagues, Kunal Bahl, did quit Microsoft when his H-1B ran out and his green card had not yet arrived.
"He returned to India and then founded Snapdeal, which today is worth more than $1 billion and employs five thousand people. Ironically, online, cloud-based companies like Snapdeal would play an important role in my future and that of Microsoft. And the lessons I learned in my former country continue to shape my present," he says.
Giving an insight into his childhood, Mr Nadella says that by 12th grade, his dream was to play cricket for Hyderabad and eventually work for a bank.
Mr Nadella was a student of Hyderabad Public School (HPS).
"By 12th grade if you had asked me about my dream it was to attend a small college, play cricket for Hyderabad, and eventually work for a bank. That was it. Being an engineer and going to the West never occurred to me," he says.
Mr Nadella says his mother was happy with those plans but dad advised him to get out of Hyderabad.
He writes that the list of alumni from the Hyderabad Public School speaks for itself.
"Shantanu Narayen, the CEO of Adobe; Ajay Singh Banga, the CEO of MasterCard; Syed B Ali, head of Cavium Networks; Prem Watsa, founder of Fairfax Financial Holdings in Toronto; parliament leaders, film stars, athletes, academics, and writers - all came from this small, out-of-the-way school," he adds.