Right, so I am tinkering with a Human idea, but some stuff on lore about pre-Booty Bay isn't necessarily clear to me.
It states in Wowpeadia that in order to try opening trade routes Stormwind sent Humans into Stranglethorn and they made a settlement called Blackwater Cove. Then some Trolls came and killed/drove off the Humans, and then later the Goblins came in to drive the Trolls away and then formed Booty Bay. I have never played the WC games, so I don't know exactly -when- this happened. All I know is that Booty Bay was there since Vanilla WoW.
So...when in our timeline did Blackwater Cove get set up and overrun by Trolls?
There's no date given for this (I actually didn't know about Blackwater Cove until this post!), but we can assume that it couldn't have happened before the Second War (where the Gobbo-lins began growing in power) and obviously didn't happen after vanilla, so we've got a 14 year window in which Blackwater Cove could've been turned into a city. Assuming that the construction and smacking of the Trolls abides by the laws of reality (which, sadly, basically nothing in WoW lore does), you'd have a few years 'fore having a settlement the size of Booty Bay. So... I dunno, an estimate would be Year 15-22?
First time I heard of it, so I tried to dig up some info.
First, I found this, where I guess the wiki info comes from:
http://pc.gamespy.com/pc/world-of-warcra...788p1.html
Quote:In recent years, the humans of Stormwind attempted to forge trade routes through this savage jungle. Though they did manage to establish the small port town of Blackwater Cove, they were quickly overwhelmed by a crazed pack of trolls and driven back to their homeland.
Definitely post-Second War, or recent years would be a silly thing to say. I'll make my own little assumptions that the trade route attempt was after the construction of Stormwind's main holdings was complete, which was year 14.
Next, something I dislike, but the World of Warcraft comic has a mention of Booty Bay. Here's the page.
http://multiplayerblog.mtv.com/wp-conten...e0_pg4.jpg
As you can see by the page, Booty Bay has already been well-established as a goblin town, and our narrator says "When Thrall led our people to our new homeland, I followed...". Since he seems to be saying that he followed Thrall there while the Third War was still going on, I'm guessing they left by year 20.
So that's six years between Stormwind's reconstruction (unless Stormwind decided to spread themselves thin, but again, the quote says "recent years") and the Third War.
I'd guess that Blackwater was fully established by year 16, destroyed that same year, and it was converted to Booty Bay a year or two later. Don't count this as an official answer, of course. I also doubt that Blizzard even considers Blackwater canon anymore.