The introduction of the bill, seeking to 'substitute Section 377 of the Indian Penal Code', was objected to by BJP member Nishikant Dubey when Tharoor moved it for introduction.
Dubey said he was opposing the bill not because of any religious considerations or Vedas or 'puranas' but because of a Supreme Court judgement.
The Supreme Court, in December 2013, had overturned a verdict of the Delhi high court that had set aside Section 377 of the IPC, asking the government to take a view on the controversial subject of decriminalising homosexuality.
The Delhi high court, in 2009, ruled that Section 377 was unconstitutional.
Tharoor, however, insisted on going ahead with the introduction of the bill, arguing that Dubey was quoting only 'partially' from the SC judgement.
Tharoor was supported by Biju Janata Dal’s Tathagata Satpathy.
However, in order to take the sense of the House, Deputy Speaker M Thambidurai put the motion to vote.
Tharoor pressed for division of votes in which the motion was negated by 71 'Noes' against 24 'Ayes'. There was one abstention.
Satpathy remarked, "It is a very sad day."
This is a rare occurrence as a bill, that too a private member one, was voted out at the introduction stage itself.
Usually, the private member bills are withdrawn after a debate and a reply by the government.
"It strikes me as extremely intolerant because at this stage, it’s a very routine procedure. I begged for leave to introduce the bill. It is extremely unfortunate for a bill to be rejected, even for introduction and it shows, I am sorry to say, the degree of intolerance that exists in sections of our ruling party," Tharoor said later.
The Congress leader and former Union minister said he 'will move the bill again when the session is convened the next time to ensure individual privacy is possible'.
The bulk of the votes opposing 'even the introduction of the bill' came from the BJP, claimed Tharoor, although he also noted that there were 'some members' of the ruling party who 'seemed to have' voted to allow him to introduce it.
Although the bill on decriminalising homosexuality was rejected at the introduction stage, Tharoor managed to introduce two other private member's bill pertaining to another amendment to the IPC and on asylum seekers.