Of course, lots of dwarfs, trolls, native people, trappers, hunters and the merely badly lost had discovered it on an almost daily basis for thousands of years. But they weren't explorers and didn't count.
"Witches Abroad" it is. I wondered if the note was too vague, but thought that there was an implication of "travel" which might be a hint.
Over to you.