This joke dates to the prime days of Usenet newsgroups, when Usenet was primarily used by university students, computer engineers, and hackers. This user base was naturally centered in major world cities, and it was rather rare to be able to access Usenet from a modem attached to a personal computer (for home users, the local dial-up BBS was much more common, avoiding the significant fees of long-distance calls). This was much different from e.g. a phone network or telegraph network which endeavored to include everyone. Awareness of this exclusivity gave rise to a perverse sense that those outside the Usenet bubble might as well not exist.

The first incarnation of the joke was posted to talk.bizarre on March 30, 1988, taking the following form:

SUBJ: North Dakota DOES NOT EXIST !!!!!

I have been told by VERY reliable sources that the alleged state of North Dakota does not exist! I can prove it to you. How many of you have ever been to North Dakota... See, none of you have ever been there, nor do you know anyone there. Its never mentioned in the news, and its just a ploy to give the U.S., an even number of stars on the flag.

(Note that the serious reply to this on the linked page was sent by an alleged North Dakotan working at an Indiana university, not from anyone residing in North Dakota.)

In 1992, a much longer Usenet essay was written denying the existence of Idaho, a rather strained parody of conspiracy logic along the lines of the present-day "Birds Aren't Real" group.

In 1994, a thread was posted to the German newsgroup de.talk.bizarre with roughly the same content about the city of Bielefeld, population 340,000. This became much more popular than the North Dakota incarnation and gave rise to the "Bielefeld conspiracy," which was one of the earliest memes of any kind (it has been referenced by Angela Merkel, four books have been written about it, and a documentary about it was completed in 2010).

The digital media scholar Yvette Granata has suggested that this type of joke is endemic to the Internet as medium, playing on the uncanny claim that every location on Earth might eventually be found in a universal computer database, and the idea that false data might be inserted into this totalizing simulacrum for nefarious purposes.