La tradició atribueix la seva fundació a Raja Launkarn, que li va donar el nom de la seva esposa Nar Laun però segons el Mahabharata el territori al sud de Delhi és anomenat Narrashtra, del que podria derivar Narnaul; els historiadors musulmans l'esmenten per primer cop al temps de Shams ad-Din Iltutmish al-Kutbi ibn Yalam Khan (1211-1236) que la va donar en feu a Malik Saif al-Din. El 1411 estava en possessió d'Iklim Khan i Bahadur Nahir, i fou saquejada per Sayyid Khidr Khan (1414-1421). Localment és considerada el lloc de naixement de Sher Shah, i el cert és que el seu avi Ibrahim Khan hi va morir i la seva tomba encara s'hi conserva. El vassall de Sher Shah, Haji Khan, fou expulsat de Narnaul per Tardi Beg a la restauració d'Humayun; en el regnat d'Akbar, Shah Kuli Mahram, va adornar la ciutat amb edificis i tancs d'aigua. Sota Aurangzeb, el 1672, Narnaul fou centre d'una revolta religiosa; un cos de satnamis, una secta en què els seus membres es consideraven immortals, va atacar la ciutat i va establir un govern, però finalment foren derrotats a costa de molt morts. Quan el poder mogol va entrar en decadència va passar a Jaipur. El 1795 fou conquerida per Appa Khande Rao i George Thomas a Lakwa Dada, un oficial de De Boigne, i fou cedida després a Murtaza Khan Bahraich. En recompensa pels seus servis al moti de 1857, Maharaja Narindar Singh de Patiala va rebre Narnaul en feu. El 1906 fou erigida en municipalitat.
