Deuteronomy does not ban homosexuality, only sacred prostitution. So the question is, when was sex among men banned?As the article notes, there is very little information about homosexuality in ancient Israel before Leviticus. Some think that the Deuteronomistic History implies a homosexual relationship between David and Jonathan, although the evidence is ambiguous. James Harding has recently published a book on the biblical material and its later interpretations: The Love of David and Jonathan: Ideology, Text, Reception (Routledge, 2013).
We cannot know with accuracy. The ban only appears in two verses, both in the same section of Leviticus (18:22 and 20:13). Most scholars believe these verses were written either during the Babylonian Exile or during the early Second Temple period, so sometime during the 6th to the 4th century BCE (2600 to 2400 years ago), but when exactly in this period, we do not know.
Nor can we know what led to this prohibition. Some speculate that it was an expansion on the ban on sacred prostitution. Others think it was an effort to limit contact between Jews and gentiles, but the fact is no-one knows.
Whatever the reason and whenever it was decreed, once it was codified in Leviticus, it became Jewish law. But does this mean that ancient Jews stopped engaging in homosexuality?
Probably not. From the end of the 4th century BCE, and later under the Romans, Jews found themselves living in cultures that practiced homosexuality between men and boys as a norm.
The question is how tolerant the rabbis were of these practices. This turns out to be a very difficult question to answer.
Beyond that, there are various hostile references to male cultic prostitutes, which show that such prostitution was common enough that the Deuteronomic and Deuteronomistic writers had to take enough notice to condemn it. Likewise, the Priestly writers would not have been likely to issue a law against male-on-male sex unless people were actually doing it.
Mr. Gilad does not seem to have found any additional references to homosexual practice before the Talmud. There certainly don't seem to be many. A few are collected in an essay by Preston Sprinkle which I noted last year here. And even some of these are dubious. I am not sure that Pseudo-Phocylides, 2 Enoch, or Sibylline Oracles 3 and 5 give us evidence for Second Temple Judaism. But that still leaves passages from the Damascus Document (reconstructed, but plausibly), Philo, and Josephus (but Ant. 1.200-201 is not relevant - typo?), as well as a comment in the Letter of Aristeas (whose text, however, is somewhat in doubt) and one reference in the Mishnah. All of these passage condemn male-on-male sex, which, again, does seem to indicate that it was something that happened often enough to require condemnation. Incidentally, in Laws 3.41, Philo makes what must be one of the earliest surviving references to transsexual surgery.
Also, here's an old post in which I discuss the Leviticus passage in detail.