Nulogorsk is a tiny fishing village in Russia that once served as a sister city of Night Vale, sharing pen-pal letters and gifts with Night Vale for many years. However, in 1983, the citizens of Nulogorsk stopped changing the dates on their letters. In 1997, after fourteen more years of correspondence, the citizens of Night Vale concluded that Nulogorsk would "never stop existing in 1983," and lost interest in communicating with the small Russian village, as they were unable to discuss contemporary developments in Michael Jackson's career with people who were stuck in 1983.
On February 1, 2014, relations between Nulogorsk and Night Vale were resurrected with the arrival of a beached Nulogorskian submarine in Night Vale's Sand Wastes. The arrival of a Nulogorskian submarine in Night Vale's desert wasteland was considered odd because the citizens of Night Vale had not corresponded with the citizens of Nulogorsk for seventeen years, and for no other reason. The Sheriff's Secret Police opened the hatch on the submarine, and, after losing their first responder, a Junior Secret Detective, to an unexplained bout of rapid aging accompanied by inhuman, agonized screaming, discovered a strange care package from Nulogorsk. Included in the package were:
- The living body of an enormous, bald-headed man with faded flower tattoos and missing his left hand.
- A postcard depicting Nulogorsk, with a message in Russian scrawled upon the back that read, simply: "One adult man, missing hand. And the other items."
- A rotary-dial phone with no receiver cord
- A large tin full of hardtack
- A wrapped parcel, which was carried away by a man who was not tall
- A thick book, which was carried away by a man who was not short
- An anomalous, apparently a historical front page article from the September 24, 1983 edition of the Night Vale Daily Journal, suggesting that Nulogorsk had been obliterated in a nuclear explosion
Shortly after discovering the contents of the submarine, the enormous, one-handed bald man, after taking a short call on the disconnected rotary phone, explained that he was a gift from Nulogorsk, a body donor for local Night Vale resident Megan Wallaby, a young girl whose body had been, since birth, a middle-aged man's detached left hand. Soon after, the man was surgically attached to young Megan's hand-body in a procedure the surgeons called a complete success. As Megan's consciousness has apparently entirely replaced the mysterious Nulogorskian body donor's, he was unavailable to answer Night Vale's lingering questions about Nulogorsk's fate.
Nulogorsk's possible destruction
Of the items contained in Nulogorsk's submarine care package, the most disturbing was perhaps the historically anomalous September 24, 1983 Night Vale Daily Journal article, written by foreign correspondent Leann Hart, whose headline read: "Sister City Nulogorsk Decimated By Nuclear Attack: No Known Survivors." Cecil Gershwin Palmer claimed to have pulled the date's true front page article from the Night Vale Daily Journal's archives, which was headlined, "City Council Okays Book Ownership For Randomly Selected Students." Cecil didn't know which truth to believe, and wondered, if Nulogorsk had been obliterated in a nuclear attack in 1983, who exactly the citizens of Night Vale had been corresponding with for the following fourteen years.
Compounding the mystery, upon the Nulogorskian submarine's arrival but before its opening, the genderless spokesbeing for the Sheriff's Secret Police had delivered a bizarre, aimless public announcement which, in retrospect, seems to be a second-person description of a Nulogorskian child's last memories before dying in a nuclear explosion with their grandfather.
Behind the scenes
The Welcome to Night Vale episode that introduced Nulogorsk is one of several episodes co-written by Something Awful's Zack Parsons. Those familiar with his work may remember his serial sci-fi horror story, That Insidious Beast, which also prominently featured a horrifying overlap between alternate realities, and also used an impossible newspaper headline from a disparate reality as a source of horror.
As far as the etymology of the name Nulogorsk, the "-gorsk" suffix is a Russian equivalent of "-ville" or "-burg", denoting the name of a town, and "nul" means "zero" or "null". So an English translation of Nulogorsk might be "Nullville" or "Zeroville". The phonetic similarity of the former to Night Vale is likely not coincidental.
Another possibility comes from the name the word 'gora' (гора), origin of the name Gorsky. 'Gora' translates to mountain, which could lead Nulogorsk to be interpreted as 'No Mountain'. This in turn refers to the ongoing debate in Night Vale over the existence/non-existence of mountains.
On September 24th of 1983 the Soviet Union did have five underground nuclear tests. Earlier in the same year the NATO naval exercises known as Able Archer led Russia to ready their nuclear weapons. 
On September 26, 1983, the nuclear early warning system of the Soviet Union twice 'falsely reported the launch of American Minuteman intercontinental ballistic missiles.