อำเภอศรีเมืองใหม่ เดิมมีฐานะเป็นเมืองชื่อ "เมืองโขงเจียม" ก่อนที่จะเปลี่ยนชื่ออำเภอศรีเมืองใหม่ใน พ.ศ. 2500 โดยศรีเมืองใหม่เป็นเมืองที่มีประวัติความเป็นมาอันยาวนาน มีกลุ่มคนดังเดิม เผ่าชนพื้นเมือง เผ่าบลู ส่วย ลาว เมื่อปลาย พ.ศ. 2314 กลุ่มคนอพยพหนีจากเมืองนครเขื่อนขันธ์กาบแก้วบัวบาน ลงมาทางใต้โดยแยกออกเป็น 2 กลุ่ม คือ กลุ่มเดินทางมาทางบก ได้มาตั้งถิ่นฐานอยู่ที่ดอนมดแดงอันเป็นที่ตั้งของเมืองอุบลราชธานีในปัจจุบัน อีกกลุ่มหนึ่งอพยพลงมาตามลำแม่น้ำโขงมาตั้งบ้านเรือนอยู่ที่ดอนหินตั้ง เพื่อประกอบอาชีพทำไร่ทำนา ทำสวน เดิมทีชื่อ "บ้านโขลงเจียง" โดยมี สมมุติฐานจาก ประวัติศาสตร์ลาว เขตนครจำปาศักดิ์ ใน พ.ศ. 2256 สมัยเจ้าสร้อยศรีสมุทร พุทธางกรู (เจ้าหน่อกษัตริย์) ได้แต่งตั้งให้ท้าวหลวง ซึ่งเป็นบุตรพระละงุมให้เป็นขุนนักเฒ่า ไปรักษา "บ้านโขลงเจียง" โดยทั่วไปชาวบ้านเรียกบ้านโขลงเจียงว่า บ้ามเจียมใต้ มีผู้ปกครองกี่คนในช่วงต่อมาไม่ปรากฏ ครั้นถึงสมัยของขุนนักราชมาอินทร์ผู้รักษา "บ้านโขลงเจียง" ได้กระทำความผิดฉกรรจ์ เจ้าเมืองนครจำปาศักดิ์ (โย่) จึงจับมาลงโทษปลดออก แล้วจึงมีหนังสือกราบบังคมทูลพระบาทสมเด็จพระพุทธเลิศหล้านภาลัย ขอตั้งท้าวมหาอินทร์บุตรขุนนักอินทวงษ์ ให้เป็นพระกำแหงสงคราม แล้วยกฐานะ "บ้านโขลงเจียง" ขึ้นเป็นเมือง "โขงเจียม" โดยขึ้นตรงต่อนครจำปาศักดิ์ใน พ.ศ. 2364

ต่อมาใน พ.ศ. 2369 เกิดขบถอนุวงศ์แห่งนครเวียงจันทร์ เมื่อพระบาทสมเด็จพระนั่งเกล้าเจ้าอยู่หัวได้ปราบกบฏเสร็จสิ้นแล้ว ใน พ.ศ. 2371 จึงได้โปรดเกล้าฯ ให้เมืองโขงเจียมขึ้นตรงต่อเมืองเขมราฐในคราวปรับปรุงการปกครอง ต่อมาในรัชสมัยพระบาทสมเด็จพระจุลจอมเกล้าเจ้าอยู่หัว ระหว่าง พ.ศ. 2443-2445 ได้มีการลดฐานะจากเมืองโขงเจียมเป็นอำเภอโขงเจียมขึ้นกับจังหวัดอุบลราชธานี

ในสมัยพระกำแหงสงครามเป็นผู้ปกครองเมืองโขงเจียม ได้ไปตั้งบ้านใหม่ขึ้นอีกบ้านหนึ่งชื่อว่าบ้านเจียมเหนือ สันนิษฐานว่าเป็นบ้านนาแวง ตำบลนาแวง อำเภอเขมราฐ ในปัจจุบัน ทั้งนี้อาจสืบเนื่องมาจากการเก็บส่วย ในเขตรับผิดชอบมีอาณาเขตกว้างขวางไม่สะดวกในการเก็บส่วย พระกำแหงสงครามได้อยู่รักษาบ้านเจียมเหนือตลอด ส่วนบ้านเจียมใต้ได้มีผู้รักษาบ้านเจียมใต้สืบต่อมา ซึ่งชื่อของผู้รักษาบ้านเจียมใต้ได้แก่ หลวงเจ้าก่ำ, พระคง, อุปฮาดจันทา

ต่อมาในปี พ.ศ. 2444 ได้เกิดกบฏผีบุญ ซึ่งขณะนั้นเจ้าอุปฮาดจันทา เป็นผู้รักษาเมืองถูกฆ่า เมื่อบ้านเมืองสงบ พระบาทสมเด็จพระจุลจอมเกล้าเจ้าอยู่หัวได้โปรดเกล้าฯ แต่งตั้งท้าวบุญธิสารวงษ์เจียม เป็นนายอำเภอคนแรกของอำเภอโขงเจียมใน พ.ศ. 2454

ใน พ.ศ. 2450 ไทยเสียดินแดนฝั่งขวาของแม่น้ำโขงให้ฝรั่งเศส ชาวบ้านที่รักความเป็นไทได้พากันอพยพเข้ามาตั้งบ้านเรือนที่บ้านคันนกหอ ให้ชื่อว่าเมืองสุวรรณวารี โดยการนำของเจ้าอุปฮาด( คำพัน) และพระอุบลกิจประชากร ช่วงนั้นอำเภอโขงเจียมได้แบ่งการปกครองออกเป็น 3 ส่วนคือ

• ส่วนที่ 1 ท้าวบุญธิสาร วงษ์เจียม อยู่บ้านนาคอ มีหน้าที่เก็บส่วย 7 ตำบล คือ ตำบลสำโรง ตำบลนาโพธิ์กลาง ตำบลหนามแท่ง ตำบลลาดควาย ตำบลสงยาง ตำบลวารินชำราบ ตำบลเอือดใหญ่ ตำบลนาคำ
• ส่วนที่ 2 พระราชพงศา อยู่ที่บ้านคำไหล บ้านจารย์ทัย หรือเมืองวารินชำราบ ปัจจุบันตั้งอยู่ในเขตอำเภอศรีเมืองใหม่ มีหน้าที่เก็บส่วย ตำบลวาริน และตำบลคำไหล
• ส่วนที่ 3 เจ้าอุปฮาด (คำพัน) อยู่ที่บ้านคันนกหอ ถูกยกฐานะเป็นเมืองสุวรรณวารี มีหน้าที่เก็บส่วย ตำบลบ้านด่าน และตำบลห้วยยาง

ใน พ.ศ. 2457 ท้าวบุญธิสาร วงษ์เจียม กระทำความผิดทางราชการจึงสั่งปลดหลวงศรีอาชญาซึ่งอยู่บ้านสุวรรณวารี ได้รับแต่งตั้งให้เป็นนายอำเภอโขงเจียม จากนั้นจึงได้ย้ายที่ว่าการจากบ้านนาคอ ตำบลหนามแท่ง (เขตศรีเมืองใหม่ในปัจจุบัน) ไปตั้งที่ทำการอยู่เมืองสุวรรณวารีและเปลี่ยนชื่ออำเภอโขงเจียมว่าอำเภอสุวรรณวารี ต่อมาใน พ.ศ. 2458 เกิดฟ้าผ่ากุฏิวัดบ้านสุวรรณวารี ทำให้พระมี พระพันธ์ และสามเณรศรีจันทร์ ถึงแก่มรณภาพไปพร้อมกับไฟไหม้กุฏิ ในปีเดียวกันนั้นหลวงศรีอาชญา ผู้เป็นนายอำเภอชรามากจึงได้ถึงแก่กรรม พวกชาวบ้านพากันขวัญเสียหาว่าเป็นเมืองอาถรรพ์จึงพากันอพยพหนีและเห็นว่าสถานที่ตั้งอำเภอสุวรรณวารี ที่เดิมไม่เหมาะสมจะเป็นที่ตั้งอำเภอต่อไป จึงพิจารณาเลือกเอาบ้านด่านปากมูลเป็นที่ตั้งที่ทำการอำเภอแห่งใหม่ แต่ยังคงเรียกว่า อำเภอสุวรรณวารี เช่นเดิม โดยสาเหตุที่เลือกเอาบ้านด่านปากมูลเป็นที่ตั้งอำเภอ เพราะบ้านด่านปากมูลตั้งอยู่ที่ปากแม่น้ำมูลซึ่งไหลมาบรรจบแม่น้ำโขงอันเป็นเส้นทางคมนาคมที่เข้าสู่จังหวัดอุบลราชธานี จึงสะดวกแก่การตรวจตราบุคคล และสินค้าที่ผ่านเข้าออกระหว่างประเทศไทยกับประเทศลาว (เป็นอำเภอที่ย้ายที่ทำการบ่อยครั้งทั้งในเขตอำเภอศรีเมืองใหม่ปัจจุบันและเขตอำเภอโขงเจียม)

ใน พ.ศ. 2458 ทางราชการได้แต่งตั้งให้หลวงแกล้วกาญจนเขต (ม.ร.ว.คอย อรุณวงศ์ ณ อยุธยา) เป็นนายอำเภอสุวรรณวารี ต่อมาใน พ.ศ. 2482 ทางราชการได้เปลี่ยนชื่ออำเภอสุวรรณวารีเป็นอำเภอโขงเจียม เพื่อรักษาชื่อเมืองโขงเจียมเดิมไว้

ใน พ.ศ. 2500 นายผล ไตรสาร ซึ่งเป็นนายอำเภอโขงเจียมขณะนั้น ได้ย้ายที่ว่าการอำเภอโขงเจียมไปตั้งที่บ้านคำบอน (ร่องคำหมาจอก) ตำบลนาคำ ซึ่งเป็นที่ตั้งที่ว่าการอำเภอศรีเมืองใหม่ ในปัจจุบัน จัดการการปกครองเป็น 7 ตำบลคือ ตำบลนาคำ ตำบลวาริน ตำบลคำไหล ตำบลสงยาง ตำบลเอือดใหญ่ ตำบลลาดควาย และตำบลหนามแท่ง

สาเหตุที่ย้ายที่ทำการอำเภอไปตั้งที่บ้านคำบอน เนื่องจากพิจารณาเห็นว่าที่ตั้งอำเภอเดิมไม่ได้เป็นศูนย์กลางในการปกครองหมู่บ้าน ไม่สะดวกต่อการติดต่อประสานงานในระดับอำเภอและจังหวัด ที่ว่าการอำเภอตั้งอยู่ที่ร่องคำหมาจอก อำเภอโขงเจียม และขณะเดียวกันที่ตั้ง อำเภอโขงเจียมเดิม ซึ่งตั้งอยู่ ณ บ้านด่านปากมูล ทางราชการประกาศตั้งให้เป็น กิ่งอำเภอบ้านด่าน มีเขตปกครองแบ่งได้ 3 ตำบล คือ ตำบลโขงเจียม ตำบลห้วยยาง และตำบลนาโพธิ์กลาง มีนายจิตร สุวรรณไลละ ทำหน้าที่เป็นปลัดอำเภอหัวหน้ากิ่ง ต่อมาในปีพ.ศ. 2502 ได้รับยกฐานะให้เป็นอำเภอบ้านด่าน มีเขตการปกครองแบ่งได้ 6 ตำบล คือ ตำบลโขงเจียม ตำบลคำเขื่อนแก้ว ตำบลหนองแสงใหญ่ ตำบลห้วยไผ่ ตำบลห้วยยาง และตำบลนาโพธิ์กลาง

เมื่อวันที่ 25 กันยายน พ.ศ. 2514 ทางราชการได้พิจารณาเห็นว่า คำว่าโขงเจียม ชื่อดั้งเดิมอำเภอบ้านด่าน เพื่อความเหมาะสม จึงได้พระราชทานนามอำเภอโขงเจียมในขณะนั่นใหม่ ชื่อ "อำเภอศรีเมืองใหม่" แล้วคืนชื่อโขงเจียมให้กับชาวกิ่งอำเภอบ้านด่าน ซึ่งเป็นที่ตั้งของบ้านด่านปากมูล ชื่อใหม่เป็น "อำเภอโขงเจียม" อีกครั้งจนถึงปัจจุบัน โดยคำว่า "ศรีเมืองใหม่" หมายถึง ที่อยู่อาศัย (เมือง) ที่สร้างขึ้นใหม่ ที่เพียบพร้อมด้วยความสุขความเจริญและความสง่างาม"