The Deep Web began and was known as the "Hidden Web". It's also called the Deepnet, Invisible Web and Hidden Web.
The term was first used by Mike Bergman, founder of BrightPlanet. He was credited with coining the phrase in a seminal paper on the deep web published in The Journal of Electronic Publishing. It was mentioned that Jill Ellsworth used the term invisible web to refer to websites that were not registered with any search engines.
The Deep Web is not indexed by search engines because information in it is dynamically generated. Pages inside the Deep Web do not exist until they are created dynamically as the result of a specific search.
Bergman said that searching on the internet today can be compared to dragging a net across the surface of the ocean. "A great deal may be caught in the net, but there is a wealth of information that is deep and therefore missed." This is because most of the web's information is buried far down, below the Surface Web (Clearnet, the visible Web or indexable Web: the web that can be indexed by conventional search engines) that most people are accustomed to.
The exact size of the Deep Web is debated. But it is believed that Deep Web is larger by several orders of magnitude than the Surface Web. Many information on the Deep Web cannot be found on the Surface Web.
However, some people believe that the origin of the Deep Web goes back to the 1990s, with the creation of "Onion Routing" by the U.S. Naval Research Laboratory. The creation of Onion Routing was the first step toward the Tor Project.