Why aren't new stars in Earth's relative proximity constantly discovered? Okay, bear with me. In layman's terms:

The estimates vary, but on a clear night, away from big cities, one can see up to 5000 stars in the sky. All those are in the Milky Way, but they're hardly equidistant from Earth, which would mean that they revolve around the galactic center at different orbits. According to some sources, some are positioned very closely to us while others hang out as far as 1000 light year away.

Now by astronomical standards, 5000 stars is not a great number. It's still pretty impressive, though.

Some stars are larger, and others are smaller. It stands to reason that some of them might be "hiding" behind others. Because they all orbit the galactic center at different speeds, using different orbits, wouldn't it follow that from time to time, over the centuries, decades, or even years (months?) a "new" star would emerge from behind another one? Shouldn't this be happening often; or are they so sparsely distributed around the galaxy that no "new" stars have appeared out there over the past three thousand years or so?
To the naked eye, the answer is almost certainly no because of the enormously slow movement of stars across the sky and because 5,000 stars may be a lot but only a tiny percentage of the sky is covered by visible stars.

To Hubble, which can see perhaps tens of millions of stars, maybe more, the link here, has a picture of two stars that are approaching crossing each other's path from our point of view.  With a big enough telescope it probably happens from time to time, though I wouldn't want to try to calculate how often, but to the naked eye, I'm comfortable saying no, in fact, it was often assumed that stars didn't move and were fixed in the sky (contrary to what Macrobius said).  That was the popular point of view prior to Halley's observation.   

There was also Tycho Brahe's "De Nova Stella" or "new star" which we now know to be a super-nova, and that was quite the surprise at the time.   Nobody thought a new star could appear because they thought the stars were fixed and permanent, but that appearance wasn't by the method you suggest.

Consider how small stars are from our point of view.    Alpha Centauri A, the larger one, it's about 1.7 million KM across and it's about 4.3 light years away, or, 41 trillion KM.   It's diameter is 23 million times smaller than it's distance from us.  That's the equivalent of looking at a golf ball from nearly 200 miles away.    Now if you scatter 5000 golf balls each 200 miles away across the sky and you let them move around very very slowly, how often do you think one golf ball passes in-front of another?   Not very often.   Granted, that's not quite right as the atmosphere spreads stars out a bit so each golf ball is smudged to maybe the size of a basketball, but they almost never pass infront of one another, at least, not if we only take into account 5,000 visible stars.  

Now, binary stars, it happens more often if they are lined up right, then they can pass infront of each other and this has certainly been observed by telescope but not to the Naked Eye, we can't visibly tell that Alpha Centauri is 2 stars (3 with the more distant Proxima but that can't be seen by the eye).  They are on average about a billion miles apart but that can't be seen by the naked eye.   It was observed by telescope in 1689.

There simply aren't enough visible stars (and taking HDE's point that most of the 5,000 visible stars weren't cataloged until recently), there's essentially zero chance that it was ever observed that a star appeared "new" by passing from behind another star.

Using Hubble, it can happen, but not to human sight.