Was it one band, or is this more tied to a particular genre or era of time?
Strangely enough, present-day rock concerts are an offshoot of the Western European classical music tradition, which has a lineage that can fairly reliably be traced back to the fall of the Roman empire (476 AD). Depending on who you ask, this lineage can be traced even further back to the ancient Greeks and ancient Egyptians.
If that's a stretch, consider the tradition of Italian opera in the mid 19th century -- the notion of divas showboating and repeating arias at the audience's insistence is well-documented, and into the 18th century we have supervirtuosos such as Franz Liszt and Niccolo Paganini who were known for over-the-top theatrics during their concerts (playing encore after encore, etc.).
As you go further back in time, a shift starts to happen -- whereas today we see famous musicians in many ways like royalty, the reality of the situation hundreds of years ago was that musicians were exclusively in the employment of royalty. All this means for the encore is that instead of musicians coming back on stage to please their audiences, musicians are being ordered to play a piece of music again by the King. One easily-recalled example of this is the famous premiere of Handel's Water Music, which King George I ordered be repeated at least three times.
Let's not forget, also, that the word encore literally means "again" in French... So the "encore tradition" is really just the idea that in performance, a musician might change the program at the request of the audience. And when your audience is royalty, your life effectively depends on you doing what they want.
So as far as "when did the tradition start?" is concerned, I would argue that for as long as we've had musicians and royalty to boss them around, we've had the encore tradition.