I've been doing some research on the history of usability testing. What I've found out is that it has been done at least since 1981 at Xerox(based on unreliable source of Wikipedia). Can anyone remember any earlier examples? Preferably with reliable reference.
You may need to think about what you mean by usability testing though — is it testing anything that humans have to use? or is it specifically a computing device? or is it limited to usability testing electronic interfaces?
Doug Engelbart (inventer of the mouse in 1963) did a test for NASA on the efficiency of pointing devices in the mid 60s. This may be the first, but I haven't looked further back. His work may or may not reference some earlier usability testing.
If you hit a dead end there, try getting in touch with these guys:
Usability testing has its roots in domains outside software, then called human factors or ergonomics. For when it started, I'd go back at least as far as to the second world war, when extensive testing was done on military equipment. For the first time there was explicit focus on the human operators, including concepts such as attention and fatigue. See for example a short history of human factors.
The more narrow concept of testing software applications under controlled (lab) conditions started later, but I wouldn't know exactly when or where.