Origin of "the nature of the beast"
According to the Oxford English Dictionary, the nature of the beast first appeared in the 1600s:
colloq. the nature of the beast : the (usually undesirable) inherent or essential quality or character of a person, event, circumstance, etc.
1678 J. Ray Coll. Eng. Prov. (ed. 2) 77 It's the nature o' th' beast.
John Ray's Collection of English Proverbs was a collection of proverbs from different languages, as well as a list of words, a fact noted by the title page shown here. However, it seems very possible that the phrase predates this notation. The phrase appears in a dictionary entry for nature, and the nature of the beast was used to give an example sentence.
It is possible that the phrase was well known enough that, by the time Ray compiled his list, it was an accepted idiom. However, his work is the first written usage, so we can definitely note the point at which the idiom existed. Because this is the first written usage, however, we cannot derive its origins--the phrase was written, but its precise origins were not.
That being said, the OED marks usage of beast which are related, and possibly point to the history of the phrase. In the entry of beast, two definitions are:
In early times, explicitly including man. Obs.
In later times, applied to the lower animals, as distinct from man. (First usage noted is in 1616)
The animal nature (in man). (first usage noted 1667)
The phrase the nature of the beast, having been recorded in 1678, may have been pulling on the first noted definition. That is, the nature of the beast was the inherent nature of man; that deepest essence within him. The later definitions may also work (as a beast is lower than man, "the nature of the beast" is the lower qualities within a man). The old usage of the term beast would explain the origins of the phrase--it was a normal definition of beast, which literally described the inner nature of man.
Early literal use of 'the nature of the beast'
The expression "the nature of the beast" appears in a literal sense at least as early as the middle 1500s. From a 1567 translation of Ovid's Metamorphosis by Arthur Golding:
The beastes doo breake theyr fast with flesh: & yit not all beastes neyther. / For horses, shéepe, and Rotherbeastes too liue by grasse had leuer. / The nature of the beast that dooth delyght in bloody foode, / Is cruell and vnmercifull. As Lyons féerce of moode, / Armenian Tigers, Beares, and Woolues.
From "Of a Currier and a Hunter," in A Schole of Wise Conceytes wherin as Euery Conceyte Hath Wit, So the Most Haue Much Mirth (1569), translated by Thomas Blage:
The Hunter went boldly to the Beares Denne, who put in hys dogs and rouzed him. It happened that the Beare shunned hys blowe and foorthwith strake the Hunter to the grounde: who knowing the nature of the beast to bee, to take pitie of a carcase, helde his breath and fayned him self to be dead. The beare smelled at him euerywhere, & perceyuing by no meanes any life in him, departed away.
From a 1597 translation of Achilles Statius's History of Clitiphon and Leucippe, by W.B.:
Charmides inuited vs to see this beast [a hippopotamus], Leucippe: was there also togither with vs: earnestly we did behold the beast, but he whose mind was occupied about an other matter, neuer cast his eyes from Leucippe. Therefore we iudged him to be in loue with her: and because he would haue vs stay the longer there, that hee might the more satisfie himselfe with the sight of her, he began to finde some discourses: and first hee did declare vnto vs the nature of the beast, and the maner of taking him, saying, that it was a most rauenous creature, how that he wold deuour a whole field of corne: neither is he caught without a prettie wile, for ye hunters marking in what place he accustometh to lye, to dig a pit and couer it with turfes and réeds, laying vnder it a little coale made of boords, whose doores are open to the height of the pitte, then hiding themselues vn∣till he fell in, they rush vpon a sodaine and shut the doores of the little house, and so is taken, which else by no meanes could bee caught, because he is of so great a strength:
From Gervase Markham, Cauelarice, or The English Horseman Contayning All the Arte of Horse-manship... (1607):
... yet since it is the fortune of my forward spirrit, to which you haue giuen an especiall libertie through your silence, let me be helde excused, and what you shall finde to differ either from your owne rules, or from the square of auncient practise, after you haue argued it with reason and the nature of the beast, of which I treate of, if then you haue cause to condemne me, I wil with al humblenes submit to my punnishment which I perswade myselfe shall be moste charitable, because I rather desire your loues then any other mens admirations.
From Edward Topsell, The Historie of Foure-footed Beastes (1607):
Concerning their [goats'] drinke, it is necessary for a skilfull Goat-herd to obserue the nature of the beast, and the best time and place of their watering, according to the saying of Virgill:
...
Again, it must be regarded, that the Stallion be tyed and bound fast, so that he may not cover the Mare after she is with foal, nor yet have access unto her, lest by kicking and biting he cause abortment, for many times they break their bonds asunder, and greatly trouble the females with young, therefore they are accustomed to some labour, which taketh down the heat of their lust: yet at the time that they are to couer the Mares, you must vse all diligence to awaken the drousie nature of the beast, so that with greater spirit the seede of the male and female may meet together.
...
Another point of a good swine-heard, is to sweepe oftentimes the sty, for although such be the nature of the beast [swine] that it defileth all things, and will be wallowing in the mire, yet will she also be very desirous of a clean lodging, and delight much in the same; and when they be shut up, they must not be enclosed like other beasts altogether, for one of them will throng and ly upon another, but there must be several porches and hatches to sever and distinguish their lodgings, so as the great with Pig may lie in one place, and the other ready to be delivered by themselves, free from all incursion and violence.
From Edward Topsell, The Historie of Serpents (1608):
The explycation of this riddle, will shew the whole nature of the beast [a tortoise], and of the Harpe called Chelys. For some things are related herein of the living creature, and some things again of an Instrument of Musick made upon his shell and cover. And thus much for the Tortoise in general, the Medicines I will re∣serve unto the end of this History.
From Andrew Willet, Hexapla in Danielem: That Is, A Six-fold Commentarie vpon the Most Diuine Prophesie of Daniel... (1610):
Hereby rather is signified Alexanders great celeritie, which is shadowed forth in the nature of the beast [a leopard], but more liuely expressed by wings: & he is said to haue foure wings, not two, quia nihil fuit velocius Alexandri victoria, because nothing was swifter then Alexanders victories, ...
An instance where the beast in question is the Beast of the New Testament (that is, the Devil) appears in David Pareus, A Commentary upon the Divine Revelation of the Apostle and Evangelist Iohn (1644):
Abominable sinners : such indeed are blasphemers out of the Church. But principally it agrees to the worshippers of the Beast : for they imitate the nature of the Beast, and his blasphemous mouth against God, his Tabernacle, an those who dwell in Heaven.
Abraham Wright, A Practical Commentary or Exposition upon the Pentateuch viz. These Five books of Moses: Genesis, Exodus, Leviticus, Numbers, Deuteronomy (1660) uses "the nature of the beast" to refer not to the nature of a particular beast but the nature of all beasts, in contradistinction to the nature of God:
It seems this Fall hath broke the neck of mans ambition, and now we dare not be so like God as we should be; ever since this Fall man is so far from affecting higher places than his Nature is capable of, that he is still groveling on the ground; and participates and imitates, and expresses more of the nature of the beast, than his own. Fond man that is thus cheated of an assurance of Immortality, by a false perswasion that he shall be immortal: this Eritis sicut dii hath damn'd all. The Serpent perswades him if he does but taste, he shall be as God, when he hath tasted finds himself worse than a man, a very beast; being thus at once fool'd out of his Everlastingness, and the favour of his Maker.
Early figurative use of 'the nature of the beast'
The first use I could find of "the nature of the beast" to refer figuratively to the tendencies of a certain kind of human being also appears in 1660, in Cimelgus Bonde, Scutum Regale, the Royal Buckler; or, Vox Legis, a Lecture to Traytors (1660):
It is the nature of foxes to prey furthest from their holes : but these unnatural foxes [rebels against the king], in sheeps clothing, make all their prey, both at home and abroad. All is fish which comes to their net.
And that these Rebels may still have freedom to persevere in their villanies, they cry up a free-State, as the best of all Governments, yet (mark the nature of the beast,) a free-State (say they) is most beneficial for the people, yet not so free, but that they may, and will qualifie, and engage the persons chosen by the people, according to their free will and pleasure.
Similarly, from A Familiar Discourse, Between George, a True-hearted English Gentleman and Hans a Dutch Merchant, Concerning the Present Affairs of England (1672):
George. I will tell you, Hans, There has been grumbling at Kings and Courts, before you and I were born, and will be so when we are dead and rotten. It is the nature of the Beast, (the common people) to be perpetually complaining of the Times, and of the Government. But beside; Here is a sort of ill-natur'd and ill-nurtur'd people in this Nation, who would speak evil of, and despise even the Son of God himself, if he should be sent to Rule over this Kingdom.
And from Samuel Parker, A Reproof to the Rehearsal Transprosed, in a Discourse to Its Authour by the Authour of the Ecclesiastical Politie (1673):
But the King has so obliged the Non-conformists by his late mercy, that if there were any such Knave, there can be no such fool among them, that would ever lift up an ill thought against him. Now indeed you have nickt it to purpose, next to their being hang'd nothing can secure their Loyalty like gratitude and good∣nature. They lift up an ill thought against the King after he has so much obliged them! It is impossible! It is against the nature of the Beast! Away with the Guards! Save so much money! the Presbyterian has pass'd his word, and can you desire a better hostage? Oblige him but once, and he is your own for ever. It is not in his power to do an ungrateful action, and now he is so much beholden to the King, he is no more able to lift up a disloyal thought against him than to remove mountains. This I must confess goes a great way, and as far as any thing next to the Oaths of Allegiance and Supremacy, but yet after all it will not do so effectually as hanging, for what if the King should ever happen to disoblige them again? why then, unless they are very weary there is an end of all the Presbyterian Loyalty.
Application of the expression to a particular person appears in The Woman Turn'd Bully, a Comedy (1675):
Goodfeild. Gad, ye have done well. Did you but know the nature o'the beast, you wou'd not fancie him for a Father-in-Law, of all men living.
All of the instances in this subsection of my answer antedate the earliest figurative occurrence mentioned in the OED, as cited in simchona's answer, which is "It's the nature o' th' beast," in John Ray, A Collection of English Proverbs (1678), in a chapter titled "An Alphabet of Joculatory, Nugatory, and Rustick Proverbs."
Conclusions
The phrase "the nature of the beast" was surely familiar to sixteenth- and seventeenth-century English readers (and probably also to English listeners) as a literal expression of the behavior or habits of particular types of animals. The phrase goes back at least to 1567 in its modern spelling; instances containing variant or obsolete spellings may go back farther still.
Although figurative use of "the nature of the beast" to refer to human behavior is more recent, it still dates at least to 1660 (alluding to a particular class of people) and to 1675 (referring to a particular individual person). John Ray's inclusion of "the nature o' th' beast" in a list of "Joculatory, Nugatory, and Rustick Proverbs" in 1678 suggests that figurative usage of the phrase in everyday speech may go much farther back than the earliest examples I found.
"Tis the nature of the beast" In my memory of the '40s, my mother told us there was a poem written spoofing the Mother Goose rhymes, called Father Goose--Father Goose was taking care of the children and trying to answer all the questions, and his most often answer was "'tis the nature of the beast". I remember most vividly, "Why does the donkey bray, Papa, why does the donkey bray?" "Tis the nature of the beast, my love, 'tis the nature of the beast."
I've thought of it often lately.