Na místě dnešního chrámu stával již od 3. století kostel svatého Marka. V roce 620 se zhroutil, s největší pravděpodobností kvůli zemětřesení. V 7. století byla postavena současná stavba, inspirovaná formou i názvem slavným chrámem Hagia Sofia v Konstantinopoli. V roce 1205, kdy město dobyla čtvrtá křížová výprava, byla Hagia Sofia přeměněna na katedrálu. Tento status jí vydržel do roku 1224, kdy město osvobodily prapory Epirského despotátu pod vedením Theodora Komnena Doukase. Po dobytí Soluně osmanským sultánem Muradem II. dne 29. března 1430 byl kostel přeměněn na mešitu nazvanou Ayasofya Camii. Po osvobození Soluně v roce 1912 byl obnoven kostel.
Hagia Sophia je postavena jako bazilika s kupolí. Sloupy střední lodi jsou vytaženy do stran, takže centrální prostor chrámu má tvar rovnoramenného kříže. Lze jej tak považovat za přechodnou formu mezi kupolovou bazilikou a vepsaným křížovým tvarem, který dominuje byzantské církevní architektuře od 10. století. Spolu s kostelem Agia Theodosia, klášterem Wallentos v Konstantinopoli a zničeným kostelem Dormition v Nicaea představuje Hagia Sophia v Soluni jeden z hlavních architektonických příkladů tohoto typu architektury, docela známého v byzantském období.
V obrazoborecké éře byla apsida kostela zdobena prostými zlatými mozaikami pouze s jedním velkým křížem. Kříž byl v letech 787-797 po vítězství ikonodulů nahrazen obrazem Bohorodičky.
