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.