It is estimated that Namhae was part of Gunmiguk or Naknoguk among 12 tribal statelets of Byeonhan Confederacy during the Samhan Period.
It is estimated that during the Gaya Confederacy Period, among 6 Gayas, Namhae was part of Goryeong Gaya which is around Jinju now.
The very first historical records of Namhae-gun starts to appear in the Unified Silla Dynasty period, during the 7th year (687) of King Shinmun's reign. During that time, Namhae Island was called Jeonyasan-gun and was kept under the jurisdiction of Cheongju (currently, Jinju) and a Taesu (provincial governor) ruled over the region which was then divided into 2 hyeons (Nanpo-hyeon, Pyeongsan-hyeon). Then, according to the reorganization of the administrative district system in the 16th yearof King Gyeongdeok's reign, the region was given the name Namhae-gun and was put under the jurisdiction of Gangju.
Due to a nationwide administrative district reorganization in the 8th year (1018) of Goryeo King Hyenjong's reign, Namhae-gun was renamed as Namhae-hyeon and a hyeon governor ruled over the region. However, in the late Goryeo Dynasty Period, Namhae was often subjected to Japanese invaders' attacks and it became impossible to run the administration properly. So, King Gongmin who was the king in the 31st year of the Goryeo Dynasty, moved Namhae's administrative office to Daeyacheon Bugok in Jinju.
During the 13th year (1413) of Joseon Dynasty's third king, Taejong's reign, due to a nationwide administrative district reorganization, Namhae-hyeon was temporarily combined with Hadong and was called Hanam-hyeon. Then, when Hadong-hyeon became an independent hyeon, Namhae was combined with Jinjju's Geumyangbugok and was called Haeyang-hyeon and later, when Geumyang was merged into Jinju, Namhae-hyeon became an independent hyeon once again.
During that time, Namhae was under the jurisdiction of Woodo Island in Gyeongsan Province and under the jurisdiction of a Jong-2-pum (2nd rank junior officer), Magistrate of Gyeongju; Jeong-3-pum (3rd rank senior officer), Changwondaedohobusa (governor of Changwon, the capital of Gyeongsannam-do Province); and a Jong-5-pum (5th rank junior officer), hyeon governor under a Jeong-3-pum (3rd ran senior officer), Jinjumoksa (governor of Jinju-mok). In the first year of the 7th King, Saejo's reign, the local defense organization was reformed and in the 12th year (1466) of King Saejo's reign, the administrative organization was reformed, Namhae Hyeonryeong (governor of Namhae-hyeon) was in charge of Namhae region's military as a Jeoljaedowi (one of the military ranks) under the command of Cheomjeoljaesa which was ‘Jinjumoksa of jinjujingwan (commander of Jinju)'. The navy in Namhae region was in charge of Pyeongsanpomanho under the command of Wooncheongcheomsa which was the commander of Jaepojingwan. The region was one of the major battlefields for over 7 years during the Imjin War and Jeongyu War and was an uninhabited land for some time as well. In the 32nd year (1895) of King Gojog's reign, Namhae-hyeon was renamed to Namhae-gun and in 1906, Changseon-do Island which belonged to Jinju-mok was incorporated into Namhae-gun, making Namhae-gun comprised of 8 myeons.
In 1973, Galdo Island of Yidong-myeon was absorbed into Tongyeong-gun and in 1979, Namhae-myeon was raised to the status of ‘eup', making Namhae comprised of 1 eup and 7 myeons. In April 1, 1986, Sangju Local Office of Yidong-myeon was elevated to Sangju-myeon and Mijo Local Office of Samdong-myeon elevated to Mijo-myeon, making Namhae County comprised of 1 eup and 9 myeons.