By "band" I mean "A group of people, usually four or five, who play songs they composed to an audience, sometimes as a way to earn a living". That is, I don't mean orchestras or choirs, just bands. If you know a relevant example that doesn't fit the definition, feel free to add it.
In the western world, it arguably would have been around the time of the formation of a guild for musicians (minstrels) in Vienna in 1288 - Nikolai Bruderschaft (St. Nicholas Brotherhood). This was the first recorded guild for musicians.
Some info and a few references here.