ชาวเกาะกงทั้งที่มีเชื้อสายเขมรและไทย เรียกเมืองหลักนี้ว่า เกาะกง ซึ่งทั้งคำว่าเกาะและกงมีความหมายตรงตัวว่า "เกาะ" ต่อมาเมื่อช่วงที่เกาะกงอยู่ภายใต้อิทธิพลของกรุงสยาม รัชสมัยพระบาทสมเด็จพระจอมเกล้าเจ้าอยู่หัว ได้พระราชทานนามเมืองแห่งนี้ว่า ปัจจันตคิรีเขตร[3] ซึ่งมีความหมายว่า "ปลายเขตแดนที่ภูเขา" และตั้งนามเมืองให้คล้องกับเมืองประจวบคีรีขันธ์ (เดิมชื่อ บางนางรม) ซึ่งเมืองทั้งสองตั้งอยู่ในแนวรุ้งเดียวกัน[4] ดังปรากฏไว้ความว่า[5]

"...ขุนสารประเสริฐรับพระบรมราชโองการใส่เกล้าฯ ทรงพระกรุณา โปรดเกล้าฯ สั่งว่า เมืองบางนางรมนั้นโปรดเกล้าฯ ให้เรียกเมืองประจวบคีรีขันธ์ กับที่เกาะกงนั้น โปรดเกล้าฯ ให้เรียกว่า เมืองปัจจันตคิรีเขตร ให้กรมวัง หมายไปยังกรมพระกลาโหม กรมท่า กรมพระศุภรัต สัสดีซ้ายขวา ให้เรียกชื่อเมืองทั้ง ๒ ให้ถูกตามแบบรับสั่ง"

ต่อมาในรัชสมัยพระบาทสมเด็จพระนโรดม สีหนุ ทรงพระราชทานนามให้เมืองนี้ใหม่ว่า เขมรภูมินทร์[6] มีความหมายว่า "เขตแดนของกษัตริย์กัมพูชา" ซึ่งปัจจุบันยังคงใช้ชื่อนี้อยู่[7] แต่กลับไม่เป็นที่นิยมเรียกนัก ประชาชนส่วนใหญ่ยังนิยมเรียกเมืองนี้ว่า กรุงเกาะกง[7](เขมร: ក្រុងកោះកុង)

แต่เดิมที่ทำการเมืองเกาะกงตั้งอยู่ที่เกาะเสก็ดและขึ้นต่อจังหวัดกำปอต ต่อมาในปี พ.ศ. 2502 ได้มีการสร้างที่ทำการเมืองใหม่ที่เสาธงแล้วเสร็จ จึงได้แยกเกาะกงออกมาตั้งเป็นจังหวัดใหม่[7]