The Greatness of Kasi (Varanasi) and Kasi Vishwanatha Temple are described in many Puranas. Kasi is known as Avimukta Kshetra. Chapter 22 of Kotirudra Samhita of Shiva Purana describes the origin of city of Kasi and Lord Vishwanatha in detail.
During creation, Nirguna Brahman got split into a Purusha and Prakriti (Saguna form as Shiva-Shakti; metaphorically Atma and Nature). The Nirguna Brahman (Sada Shiva) ordained Suguna forms to do a Tapasya for creation of first best being.
चिदानन्दस्वरूपं च निर्विकारं सनातनम्॥ २॥
तस्यैव
कैवल्यतरोर्द्वितीयेच्छा ततोऽभवत्।
स एव सगुणो जातः शिव
इत्यभिधीयते।। ३॥
Whatever things are visible on earth as substantive, as an entity in
the form of knowledge or bliss, are eternal, free from blemish,
desired for a second. That second, of the tree of salvation, was
possessed of attributes and is called Śiva.
स एव हि द्विजो जातः पुंस्त्रीरूपप्रभेदतः।
यः पुमान् स शिवः ख्यातः
स्त्रीशक्तिः सा हि कथ्यते। ४।।
It split into two- the male and the female forms. The male is known
as Siva, while the female is shown as Sakti (Saguna forms).
चिदानन्दस्वरूपाभ्यां पुरुषावपि निर्मितौ।। ५॥
अदृष्टाभ्यां तदा
ताभ्यां स्वभावान्मुनिसत्तमाः।
तावद्दृष्ट्वा तदा तौ च स्वमातृपितरौ
द्विजाः।
महासंशयमापन्नौ प्रकृतिः पुरुषश्च तौ।। ६ ।।
O Excellent ascetics, the invisible Cita and Ananda created Purusa and
Prakrti, O Brāhmanas, on seeing their parents, both Purusa and Prakrti
developed a doubt.
तदा वाणी समुत्पन्ना निर्गुणात्परमात्मनः।
तपश्चैव प्रकर्तव्यं ततः
सृष्टिरनुत्तमा।।७।।
Thereafter a divine voice emerged out from the great Atman free from
attributes, “You perform penance, for the generation of the excellent
creation.”
Then these Purusha-Prakriti or Shiva-Shakti asked the Supreme Nirguna SadaShiva the place where they could do tapasya. The Nirguna Shiva by staying in Sky or Cosmos then created wonderful city of five Koshas in length in cosmos. Then Lord Vishnu did Tapasya in that city and waters emerged from Him and the creation happened. The Jewel of his ear fell on a place on Earth when He came back to normal state after Tapasya and that Place is known as Manikarnika which is now called as Manikarnika Ghat.
ततश्च तेजसः सारं पञ्चक्रोशात्मकं शुभम्।
सर्वोपकरणैर्युक्तं सुन्दरं
नगरं तथा।।९।।
निर्माय प्रेषितं तत्स्वं निर्गुणेन शिवेन च।
अन्तरिक्षे स्थितं तच्च पुरुषस्य समीपतः।। १० ।।
Thereafter a beautiful city was built, which was the essence of the
lustre and was spread in five kosas and was quite beautiful in which
all the amenities could be found. Siva built the city while remaining
in the sky in the firmament near the Purusa.
तदाधिष्ठाय हरिणा सृष्टिकामनया ततः।
बहुकालं तपस्तप्तं
तद्धयानमवलम्ब्य च।। ११॥
Visnu having been lodged in that city, became desirous of starting
creation. He performed tapas sitting in meditation.
श्रमेण जलधाराश्च विविधाश्चाभवंस्तदा।
ताभिर्व्यामं च तच्छून्यं
नान्यत्किञ्चिददृश्यत॥ १२॥
Because of his efforts, several streams of water emerged from that
place. At that point of time, nothing was visible there.
ततश्च विष्णुना दृष्ट्वा किमेतद्दृश्यतेऽद्भुतम्।
इत्याश्चर्यं तदा
दृष्ट्वा शिरसः कम्पनं कृतम्।। १३ ।।
Then Visnu saw as to what
was the surprising thing found there? Then he shook his head.
ततश्च पतितः कर्णान्मणिश्च पुरतः प्रभोः।
तद्वभूव महत्तीर्थ नामतो
मणिकर्णिका॥ १४॥
Then a gem emerging out of his ear fell on the ground, which was
turned into a great place of pilgrimage known as Manikarnikā.
The Cosmic Shiva held that city with His trident and placed it on Earth where Jewel fell and this city of five Koshas is called Kashi.
जलौघे प्लाव्यमाना सा पञ्चक्रोशी यदाभवत्।
निर्गुणेन शिवेनाशु
त्रिशूलेन धृता तदा॥ १५॥
When the said Manikarnikā in the form of water kept on flowing upto
five kosas (Pañcakosi), then Siva held it over the tip of his
trident.
To get rid of evil karmas and to remove bondage and to grant Moksha, Nirguna Shiva consecrated a Jyotirlinga with amsa of Him known as Avimukta Linga which grants the Moksha.
अविमुक्तं स्वयं लिङ्गं स्थापितं परमात्मना।
न कदाचित्त्वया
त्याज्यमिदं क्षेत्रं ममांशकम्॥ २१॥
Lord Śiva, the supreme soul,
there, had been consecrated as a Sivalinga known by the name of
Avimukta and spoke, “You have been formed of my amsa as Jyotirlinga
and therefore, you never leave this place.”
इत्युक्त्वा च त्रिशूलात्स्वादवतार्य हर:स्वयम्।
मोचयामास भुवने
मत्र्यलोके हि काशिकाम्॥ २२॥
Thus speaking lord Śiva, grounded Kāši, with the tip of his trident
and established it on earth.
ब्रह्मणश्च दिने सा हि न विनश्यति निश्चितम्।
तदा शिवस्त्रिशूलेन
दधाति मुनयश्च ताम्।। २३ ।।
Even after the completion of a divine
day of Brahmā, the city of Kāšî does not get destroyed. O Sages, at
that point of time, Siva holds it over the tip of his trident.
पुनश्च ब्रह्मणा सृष्टौ कृतायां स्थाप्यते द्विजाः ।
कर्मणां
कर्षणाचैव काशीति परिपठ्यते॥ २४॥
O Brähmanas, then Brahmā again recreates the universe, then he again
establishes Kāśī. Because of the bondages of the karmas and their
attraction thereto, it is called Kāši.
Nirguna Shiva then ordained Saguna Shiva to never leave this place. From that time, Suguna Vishwanatha Shiva (Shankara or Rudra) always stays at that place with Avimukteswara (formed from amsa of Nirguna Shiva).
And Lord Shiva also grants Moksha in Kashi area for the beings. Kailash Samhita of Shiva Purana in 3.2 states:
अतस्तदेव जानीयात्प्रणव सर्वकारणम् ।
निर्विकारी मुमुक्षुर्मां निर्गुणं परमेश्वरम् ।।
एनमेव हि देवेशि सर्वमन्त्रशि रोमणिम् ।
काश्यामहं प्रदास्यामि जीवानां मुक्तिहतवे ।।
Hence he who aspires for salvation and is free from aberration shall understand the Pranava as the cause of all, and Me as the Nirguna Parameshwara. I give this crest-jewel of mantras at Kashi for the liberation of all individual souls.