Transgressive sexual behaviour can of course be studied in any cultural context, and to that extent, "kink" in the broad sense is as old as humanity. Moreover, fetishism as a psychopathology is not a culturally contingent phenomenon (or even a phenomenon unique to humans, among animal species), and so it likewise necessarily lacks any clear origin point in human cultural history.
That having said, when the term "BDSM" is used nowadays, oftentimes what the speaker means to imply is an at least somewhat discrete cultural phenomenon particular to the western world of the late 20th and early 21st centuries.
The phenomenon referred to in such cases is a phenomenon which arose out of the Gay Leather subculture of the post-WWII era, in much the same crucible as that from which the motorcycle club phenomenon was born. Indeed, Gay Leather Motorcycle Clubs were an important component to the Leather phenomenon.
Because, as I say, sexual transgression has always been and shall ever be (in our species as well as others), we can readily point to earlier expressions of sexual preference resembling those which arose out of Leather. And indeed, for much of the late 20th century, the Marquis de Sade, Sacher-Masoch, and (much later) Bettie Page have been the iconic representations of BDSM which were implied to represent for it a history or a legacy. But there is no ongoing continuity to be found there. And popular BDSM historiography has therefore much revised its view of the past, over the last two decades, to recognise the specifically gay heritage of BDSM, where BDSM is deemed an ongoing cultural phenomenon represented by community institutions and organisations with their own traditions and conventions. The "Leather" label has been readopted by much of the modern BDSM community, in recognition of this.
A very important early conceptualisation of straight BDSM and BDSM involving female participants during the heyday of Leather, which played an important role in defining such a thing for popular audiences is The Story of O (French publishing, 1954, English publishing, 1965). This is important not just for its portrayal of female dominant and submissive individuals, but furthermore for its portrayal of adoption of a slave or submissive identity as a lifestyle choice (in contrast with sadomasochistic practices as a sexual activity, confined to that purpose). A name from this work is adopted by the influential early San Francisco Lesbian BDSM group Samois (see also: Society of Janus). But even here, we must resist the urge to assign too much influence to any one work.
Another work with demonstrable consequences as far as cultural exchange between the gay community and straight persons identifying as sexually transgressive is The Rocky Horror Picture Show. Again, this initially catches on in North America in 1976 as a gay phenomenon, in its characteristic midnight screenings. But straight participation and engagement with drag and gay community members emerges as a natural consequence of this, as a wider audience begins to join in. And the work's open endorsement of transgressive sexuality becomes a clarion call, for some.
Retreating from the exercise of discovering points of interchange between what already existed in Gay Leather and what was to come in (as well, Straight and Lesbian) BDSM, Townsend's 1972 The Leatherman's Handbook is a definitive and influential text of that era.
This question is somewhat tricky to answer. If by how far back in history do BDSM and other forms of kink go? you mean "how far back in time does spanking or submission or BSDM/kink actions go," then the answer is probably back into prehistory and beyond, I'm not a major believer that we're really any more or less dirty or kinky than we've ever been. There is a scene of sexual whipping in an Etrucsan tomb called the Tomb of the Whipping dating to about the fifth century BC. There are references to rough/deviant sex in Roman/Greek plays poetry such Catullus or Juvenal. In medieval times Christian penitentials were overwhelmingly concerned (more than fifty percent) with sexual sins such as period sex, oral and anal sex, lewd kissing and other forms of contact disapproved of by the church. Amusingly, the surviving records of Bishop Theodulf de Orléans asks bishops to stop asking people about these forms of sex because he believes the bishops are giving people ideas about what to do sexually. (p.s. I've found a previous discussion on this topic here.) And in the earliest surviving Renaissance works of literary pornography such as Aretino or Boccacio there are references to actions that we might call BDSM or kink or nonnormative sexualities. So that would be the answer to that question.
But if you mean "how far back in time does conscious or deliberate BDSM/kink activities and culture go," then that gives us a much more interesting and perhaps revealing answer. I would argue, in part, that the answer lies somewhere between the mid-1600s and the late 1800's with the history of libertinism and a few famous libertines that are instrumental in creating and sustaining a culture that would later develop into conscious BDSM and kink culture.
As James Turner puts it,
"Libertine[s] aspire to write the scriptures of a new religion: in the beginning was the flesh, and the flesh was made word. But these are not mere words. Though libertines sometimes disparage 'discourse' and dismiss virtue as 'nothing but language,' in fact, they revere the arousing power of rhetoric and the sensuous immediacy of what Montaigne called 'words of flesh and bone.'"
As Wikipedia puts it in their entry on Libertine, and the most clear-cut definition:
A libertine is one devoid of most moral or sexual restraints, which are seen as unnecessary or undesirable, especially one who ignores or even spurns accepted morals and forms of behaviour sanctified by the larger society. Libertinism is described as an extreme form of hedonism.
European culture in the late 17th century (1650-1700) was undergoing a dramatic shift in attitudes towards sex and sexual morality. Part of the reason for this is that moral laws began to be questioned and reinterpreted during the European Age of Enlightenment. The Protestant Reformation in England and on the Continent, along with the Catholic Counter-Reformation, had major impacts on education and philosophy, causing a shift from traditional lines of authority such as the church and Christian morality to an emphasis on reason, science, and individualism.
In regards to our topic here, both the Bible and the Old Testament began to be questioned. Specifically, the seventh commandment ("thou shalt not commit adultery") and various injunctions, from the Bible and Leviticus, against fornication, whoring, and sexual activity, began to be questioned and reinterpreted. Scientists and philosophers (in many cases one and the same, as science was still developing as a distinct field) began to question the reasons and purposes behind moral laws handed down by Scripture, especially as early anthropologists and explorers began to uncover (or claim they had) all sorts of different societal configurations from polyandry (one woman and multiple husbands) to brothel-houses containing men. The writer Daniel Defoe, who lived in Rochester's time, commented that "monogamy is a mere church imposition, a piece of priestcraft, unreasonable.” A judge who ran in Rochester's and Defoe's circles, Sir John Vaughan, declared that "No copulation of man with any woman, nor an effect of that copulation by generation [children] can be said 'unnatural.’” Even King Charles II said that he "could not think God would make a man miserable [in hell] only for taking a little pleasure out of the way."
The term libertinism was lifted out of its theological context in the late seventeenth century to describe the the court of King Charles II and the circle of sexual/freethinking high-society radicals/rakes and nobles centered around members of the Hellfire Clubs in France and England which deliberately and provocatively (albeit secretly) mocked Christianity and Christian religion by appointing the Devil as the president of the society, praising pagan idols and putting on mocking reenactments of Christian rituals such as the breaking of the bread by eating "holy ghost pie." But here is the key point: the libertines were very consciously opposing dominating morality and sexuality by acting, well, libertine, and defending their actions through their writings. The most famous of these, is of course, John Wilmot, Lord Rochester.
Dabhoiwala quotes from him at length in Origins of Sex, summing up Wilmot’s moral philosophy “in two maxims: that he should do nothing to injure himself, or to hurt another person.” He continues to explain Lord Rochester’s view that “immorality was no offence to God, for He was too great to hate His creatures, or to punish them,” and that “Religion was no more than 'the jugglings of priests'; the Bible and its miracles were but incoherent and unbelievable stories; Christian morality was only hypocrisy, obeyed by 'the rabble world' because they knew no better.” His explanation also dives in to sexuality:
It was absurd to think that humans were fallen, that 'there should be any corruption in the nature of man', or that reason was meant to restrain our physical instincts - the only true 'rules of good and ill' were those provided by our bodily senses, the only real purpose of life, to pursue happiness. It followed that the ideas of monogamy and chastity were 'unreasonable impositions on the freedom of mankind'. On the contrary, sexual pleasure 'was to be indulged as the gratification of our natural appetites. It seemed unreasonable to imagine these were put into a man only to be restrained, or curbed to such a narrowness'.
In his writing and in his poetry, Rochester and other libertines attacked rationalism, or the belief that Christianity and European culture as a whole (and its laws and norms) had reasonable or rational purposes. To libertines, the senses, not the intellect, were the greatest ability of mankind. This philosophy would be elaborated on and embraced more fully in the 18th century, especially by the Marquis de Sade.
By the time of de Sade's birth, 'libertine,' had come to mean that a person had an excessive and unfettered sex life, was frequently atheist, and attacked social and religious morals. As Phillips notes, the two men that raised Donatien were extreme libertines:
[T]he lustful Abbé enjoyed liaisons with a number of society women and even visited some of the more notorious Parisian bordellos, while the bisexual Count was on one occasion arrested for accosting a young man in the Tuileries Gardens. At the same time, both were highly cultured men. Sade's father was a close friend of Voltaire's and himself wrote verses, while Donatien's uncle in particular had a fine and extensive library which, alongside the classic authors, included all the major works of contemporary Enlightenment philosophy as well as a fair sample of erotic writings.
Indeed, as a result of their education and care, de Sade would achieve the heights of both libertinism and cultural refinement, and in his Justine, Juliette, and 120 Days of Sodom he would create absurd and ridiculous situations for his characters where he could deliberately attack Christian morality and embrace a morality of the flesh that remains unparalleled. But he also created (or sustained), or at the very least ended up popularizing a type of sexual activity that we today call sadism from his name--this is the S in BDSM, the M (masochism) comes from the name of Austrian author Von Sacher-Masoch who described the opposite situation in his Venus in Furs.
So when the late 1800's roll around and the first sexologists, Heinrich Kaan, Richard von Krafft-Ebing and Havelock Ellis, began working and defining sexuality (such as hetero vs. homosexuality, which was not categorized/defined before) and what they considered abnormal sexualities they would go on to cite the works of de Sade and von Sacher-Masoch as examples of these disordered sexualities that figures such as Sigmund Freud would attempt to treat. BDSM culture and positive self-identification with BDSM only began to develop later on in the twentieth century from the leather subculture that /u/Yst discusses here.
Sources:
My book: Annals of Pornographie: How Porn Became Bad
The Origins of Sex, Faramerz Dabhoiwala
Schooling Sex: Libertine Literature and Erotic Education in Italy, France, England--James Turner
Sade: The Libertine Novels, John Phillips
The Marquis de Sade: A Very Short Introduction, John Phillips