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.
There were humans in Northrend at least for several centuries. Ever since Northrend's introduction in w3 in backstory for Lich king it is mentioned first target for the plague were human settlements in Northrend. Wintergard almost certainly stood at least for couple of centuries since it has huge buildings, cathedral and tombs containing generations of corpses.
While humans originated from Vrykul I doubt humans of Northrend were their direct descendants that never went to Lordaeron. It is more likely that since the times of Arathor ot at the very least 1200 years since it's dissolution one of the kingdoms or several of them had sailing expeditions to Northrend and possibly attempted to colonize it. Kul Tiras ,Lordaeron and even Gilneas are good candidates. Trappers in Grizzly hills were living there long enough to have unique culture and had to be convinced to join the alliance.
As for Kalimdor it seems humans first landed there during events of warcraft 3 at least in it's Northern and Central parts where elves live. My headcanon though is that there was some knowledge among human pirates of the South Seas (we see humans in Tanaris) and Kul Tirans about the western landmass just that sailing there wasn't very profitable and Maelstrom caused major problems and was probably a huge obstacle for their earliest ships (in real life ancient ships wouldn't survive the trip to Americas even if they knew about it9. Goblins must have known about Kalimdor from early on and they traded with humans. High elves certainly knew about it and through them at least Kirin Tor. So there was awareness about it. That's why Medivh uses the term "forgotten lands of Kalimdor" rather than "unknown lands".