That is a very parochial understanding of history, which ignores women as well as other cultures than those of the region that have become "the West." Before modernity, a majority of societies had no concept of sodomy, and acts that would have fallen into the category of sodomy in the predominantly Christian nations included ones that were not only permitted but also in some cases exalted (as in ancient Greece and pre-modern Japan) or mandated in the rest of the world.*
Where same-sex sexual acts were permitted or exalted or mandated before modernity, they were largely pederasty, between older men and much younger men (often boys before the age of majority), and pederasty was often associated with pedagogy and philosophy. Older men, through their erotic engagement with beautiful young men, aspired to be one with Truth, and young men, in turn, were to be philosophically instructed by their older male admirers. Lovers and their beloveds often differed in rank as well as age: a good example is Sultan Mahmoud and his slave Ayaz (cf. <http://en.wikipedia.org/wiki/Mahmud_of_Ghazni>).
In contrast to what we know about men's sexual practice before modernity, pederasty among women does not appear to have been institutionalized anywhere, and women were less frequently prosecuted as sodomites than men, though today everyone understands that women as well as men can identify themselves as homosexual or bisexual.
Pederasty as it was practiced, and sodomy as it was prohibited, before modernity**, and homosexuality after modernity are not the same concepts at all, and the majority opinion in Lawrence v. Texas took note of the differences which outweighed a small overlap among the concepts: "It should be noted, however, that there is no longstanding history in this country of laws directed at homosexual conduct as a distinct matter. Early American sodomy laws were not directed at homosexuals as such but instead sought to prohibit nonprocreative sexual activity more generally, whether between men and women or men and men. Moreover, early sodomy laws seem not to have been enforced against consenting adults acting in private. Instead, sodomy prosecutions often involved predatory acts against those who could not or did not consent: relations between men and minor girls or boys, between adults involving force, between adults implicating disparity in status, or between men and animals" (at <http://www.law.cornell.edu/supct/html/02-102.ZS.html>).
* In anthropological literature, homosexual acts that are mandated for all men are sometimes called "institutional homosexuality." An example of it is young men sucking older men in Papua New Guinea as a part of the prescribed coming-of-age rituals, the symbolic power of semen thus being passed from the older to the younger generation.
-- Yoshie