Lord Chandrasuriyawongse (เจ้าจันทรสุริยวงษ์) and his followers established a settlement at Baan Luang Phonsim (บ้านหลวงโพนสิม) near the Thad Ing Hang Stupa (พระธาตุอิงฮัง) on the left bank of the Mekong River in Laos.

2310 (1767 Common Era), a huntsman crossed over the Mekong and arrived along the right bank at the mouth of the stream Bang Muk (บังมุก), where he discovered a discarded realm complete with a monastery and seven sugar palms on the nearby riverbank.

When he began to clear away the forests to make way for his resettlement of the realm, he found two Buddha images beneath a sacred fig tree.

Later, the iron Buddha image (the smaller one) appeared to mysteriously reestablish itself beneath the fig tree where it had first been discovered and ultimately, after some three or four spectacles of this nature, began slowly sinking into the ground there until only the crown of the head could be seen.

An alternate place of worship was built there to cover the site instead and the image itself was then named Phra Loup Lek (พระหลุบเหล็ก), or 'Venerable One of Ironmetal Who Shrouds Himself'.

During the rebuilding of the realm, at around midnight there were reports of a transparent or translucent object glittering and bright spotted emerging from the seven sugar palms.

The realm of Mukdahan at this stage covered both sides of the Mekong and reached the frontier lands of the Vietnamese (including the Laotian province of Savannakhet).

2321, during the Thonburi Period when King Taksin the Great extended his forces into the area of the Mekong River, he ordered Phra Mahakasut Suek and Chao Phya Chakri to dispatch their troops to the banks of the Mekong in order to suppress and unify the lords of all the realms great and small there on both sides of the Mekong together under the reign of the Kingdom of Thonburi, declaring Lord Chanthakinnaree the Phya Chanthasrisuraja Uparaja Mandhaturaj (พระยาจันทรศรีสุราชอุปราชามันธาตุราช), the first Lord of the Realm of Mukdahan and thereby officially naming the realm "Mueang Mukdahan".

The provincial slogan is "Skyscraping Ho Kaeo Tower, Phu Pha Thoep and Kaeng Kabao, eight ethnic minorities, famous sweet tamarind, large ancient kettledrum, origin of Lam Phaya, stunning view of the Mekong River, gateway to Indochina."

As of 26 November 2019 there are:[10] one Mukdahan Provincial Administration Organisation (ongkan borihan suan changwat) and 25 municipal (thesaban) areas in the province.