Kremvax was originally a fictitious Usenet site at the Kremlin, named like the then large number of Usenet VAXen with names of the form foovax. Kremvax was announced on April 1, 1984, in a posting ostensibly originated there by Soviet leader Konstantin Chernenko. The posting was actually forged by Piet Beertema of CWI (in Amsterdam) as an April Fool's prank—"because the notion that Usenet might ever penetrate the Iron Curtain seemed so totally absurd at the time".

Other fictitious sites mentioned in the hoax were moskvax and kgbvax. The actual origin of the email was mcvax, one of the first European sites on the internet.

Six years later, Usenet was joined by demos.su, the first genuine site based in Moscow. Some readers needed convincing that the postings from it were not just another prank. Vadim Antonov, the senior programmer at Demos and the major poster from there until mid-1991, was quite aware of all this, and referred to it frequently in his own postings. Antonov later arranged to have the domain's gateway site named kremvax.demos.su, turning fiction into truth and, according to one account, "demonstrating that the hackish sense of humor transcends cultural barriers".

During the mid-1980s, Usenet users were not aware of the official X.25 computer connections between USSR and other countries. The X.25 connections had existed since 1980, primarily via VNIIPAS and Academset to Soviet bloc countries and Austrian hosts at IIASA and IAEA. In 1983, the San Francisco Moscow Teleport (SFMT) venture was created to maintain USSR-American digital connections via VNIIPAS with its own Usenet analogues later known as Sovamnet ("Soviet-American net").

In 1992, the company Sun Microsystems, a commercial rival to VAX, gifted an own-made server to pioneer Soviet commercial network RELCOM. The company demanded that the server was named KremlSun, an allusion to then-legendary Kremvax, and made a root DNS server for the .su domain. The conditions were met, and the server became one of the initial devices when forming the Moscow Internet Exchange, since then the largest Russian Internet exchange point.