The continents of Kalimdor and Northrend were first introduced in Warcraft III. However, did the Humans know about them before that? We know that they had boats in the time of Warcraft I and Warcraft II. Did they ever try to explore the world?
It appears that the humans had not been to Kalimdor until Warcraft 3. The first noted group of humans was Jaina Proudmore's band that we see in Warcraft 3. Northrend on the other hand had human/dwarf exploration at least shortly before events of Warcraft 3, as Arthas encounters Muradin Bronzebeard when he reaches Northrend. I'm also fairly positive that Kel'thuzad had also been to Northrend prior to starting the plague in Lordaeron.
Now there are a few instances of of humans being on Northrend before we see Muradin and Arthas, but its mostly ancient history, or remnant humans. What I mean by this is that humans are supposedly related to the Vrykul (the guys we see in wrath of the Lich King) so that would mean humans left Northrend to move to Azeroth. It was also mentioned that when Ner'zul first lands in Northrend (as the Lich King) he sensed nearby human settlements, which he destroyed as the first victims of the scourge.
The only instance of a human on Kalimdor prior to Warcraft 3 I found is mention of Aegwynn being there during her battle with Sargeras, But as a Guardian of Tirisfal she was one of the most powerful mages on the planet at this time so teleporting across oceans is not unheard of for someone of her caliber.