Bill Kalush has found an early version of the trick in Denis la Marinière's La Maison Académique, 1654. It also appeared in the Asti Manuscript, c. 1700, p. 55 of the Pieper translation. This manuscript was translated in Gibecière, Vol. 8 No. 1, Winter 2013, p. 29-234. The first English appearance is in Richard Neve's The Merry Companion: Or, Delights for the Ingenious, 1716, p. 109.
The use of wax seems to be a recent development. Conjurors of the past used soap, and even chewed-up pieces of bread.
Wrapping the deck in a rubber band was introduced for practicality reasons by John Nelson in The Sphinx, Vol. 9 No. 12, Feb. 1911, p. 259. Before this time, conjurors would throw a loose deck at the ceiling, letting fifty-one cards shower down upon the audience.