I asked this in /r/askanthropology to no avail. I did a little research in my own, and it appears that the 15th century in Yemen. Can anyone validate this as true? If so, what led to the coffee bean being consumed, and by whom?
Isn't there some standard Ethiopian legend about a shepherd noticing his flock getting a little frisky around a particular bush? I know that their tradition for a long time was just to eat the cherry or chew the beans, but I don't know why it would take until 15th c. Yemen to think of putting some hot water with it.
If you mean "documented", though, maybe that was Yemen.