การก่อตั้ง NAM Air ได้รับการประกาศเมื่อวันที่ 26 กันยายน 2013 โดยเดิมทีตั้งใจให้เป็นบริษัทย่อยที่ให้บริการเต็มรูปแบบของกลุ่มสายการบินศรีวิจายาแอร์ เพื่อแข่งขันกับสายการบินแห่งชาติของอินโดนีเซียGaruda IndonesiaและBatik Airของกลุ่มLion Air ^{[ 6 ]}การก่อตั้งสายการบินนี้ได้รับการประกาศโดยประธานของศรีวิจายาแอร์ Chandra Lie ซึ่งอุทิศสายการบินนี้ให้กับบิดาของเขา Lo Kui Nam ^{[ 7 ]}

ต่อมาสายการบินได้ยกเลิกความตั้งใจที่จะให้บริการเต็มรูปแบบ โดยหันมาให้บริการเป็นสายการบินป้อนผู้โดยสารให้กับศรีวิจายาแอร์ คล้ายกับความสัมพันธ์ระหว่างวิงส์แอร์และไลออนแอร์ภายใต้ข้อตกลงนี้ ศรีวิจายาแอร์จะให้บริการเส้นทางหลัก ในขณะที่ NAM Air จะให้บริการเส้นทางรองที่ไม่ใช่เป้าหมายของบริษัทแม่^{[ 8 ]}

หลังจากการประกาศ สายการบินวางแผนที่จะเปิดเที่ยวบินปฐมฤกษ์ในเดือนตุลาคม 2556 ^{[ 9 ]}ต่อมาการเปิดตัวถูกเลื่อนออกไปเนื่องจากการรอการออกใบอนุญาตประกอบกิจการการบิน (AOC)จากกระทรวงคมนาคมของอินโดนีเซีย NAM Air ได้รับ AOC เมื่อวันที่ 29 พฤศจิกายน 2556 และทำการบินทดสอบครั้งแรกจากจาการ์ตาไปยังปังกัลปีนังเมื่อวันที่ 11 ธันวาคม 2556 ^{[ 10 ] [ 11 ]}เมื่อวันที่ 19 ธันวาคม 2556 สายการบินได้ทำการบินเที่ยวบินเชิงพาณิชย์ครั้งแรกจากจาการ์ตาไปยังปอนเตียนาคและต่อไปยังยอกยาการ์ตาด้วยเครื่องบินโบอิ้ง 737-500 ที่มีที่นั่ง 120 ที่นั่งในสองชั้น^{[ 12 ] [ 13 ]}เมื่อเปิดตัว NAM Air กลายเป็นสายการบินแรกที่อนุญาตให้พนักงานต้อนรับบนเครื่องบินหญิงใช้ฮิญาบเป็นส่วนหนึ่งของเครื่องแบบในเที่ยวบินใดๆ ก็ได้^{[ 14 ]}

NAM Air ถูกรวมอยู่ในบัญชีดำสายการบินของสหภาพยุโรปที่ไม่เป็นไปตามมาตรฐานความปลอดภัยที่จำเป็นในการบินไปยังสนามบินในสหภาพยุโรป และถูกห้ามไม่ให้ดำเนินการในน่านฟ้าของยุโรป^{[ 15 ] [ 16 ]}ต่อมาได้ถูกถอดออกจากบัญชีดำพร้อมกับสายการบินอินโดนีเซียอื่นๆ ทุกสายการบินในเดือนมิถุนายน พ.ศ. 2561 ^{[ 17 ]}

เมื่อวันที่ 8 พฤศจิกายน 2561 NAM Air และบริษัทแม่ Sriwijaya Air ได้ลงนามในข้อตกลงความร่วมมือกับ Garuda Indonesia โดยเข้าควบคุมการดำเนินงานและการจัดการทางการเงินของทั้งสองสายการบินผ่านบริษัทในเครือCitilink Indonesiaข้อตกลงนี้จัดทำขึ้นเพื่ออำนวยความสะดวกในการฟื้นฟูทางการเงินของกลุ่ม Sriwijaya Air ที่กำลังประสบปัญหา โดยการปรับปรุงการดำเนินงานและผลประกอบการทางการเงินด้วยความช่วยเหลือจากกลุ่ม Garuda Indonesia ^{[ 18 ] [ 19 ]}ข้อตกลงดังกล่าวถูกยกเลิกเมื่อวันที่ 15 พฤศจิกายน 2562 หลังจากเกิดข้อพิพาทระหว่างทั้งสองฝ่าย^{[ 20 ]}

ณ เดือนสิงหาคม2568 NAM ดำเนินการเครื่องบินดังต่อไปนี้: ^{[ 33 ]}