Bandara ini diprakarsai dan dibangun di era pemerintahan [[Samsul Hadi Siswoyo]] sebagai Bupati Jember. Pembangunan dimulai pada tahun 2003, yang telahsetelah dianggarkan sejak tahun 2001, dengan menggunakan dana APBD sebesar Rp.30 Miliar. Bandara Notohadinegoro lalu diresmikan pada tahun 2005 dengan panjang landas pacu kala itu masih 1.200 meter.
Pada tahun 2008, Bupati Jember [[MZA Djalal]] mengupayakan Bandara Notohadinegoro dapat dilayani penerbangan yang menghubungkannya dengan Bandar Udara Juanda Surabaya di Sidoarjo, sehingga dipergunakanlah pesawat udara jenisberjenis turbo LET 410 milik maskapai Tri MG International yanguntuk melayani penerbangan Jember - Surabaya pp. sebanyak 3 (tiga) kali sehari dengan sistem sewa/carter. Namun, penerbangan sewa/cartertersebutini hanya mampu bertahan selama 3 bulan dikarenakankarena okupansi yang minim sebagai akibat dari promosi yang kurang dan daya beli masyarakat yang minim saat itu. Bahkan pengoperasian penerbangan sewa/carter tersebut juga sempat dibawa ke ranah hukum karena telah mengakibatkan kerugian negara, yangsehingga menyeretakhirnya menyebabkan 3 orang pejabat Pemkab setempat masuk penjaradipenjara.
