Նաուենն առաջին անգամ հիշատակվել է 1186 թվականին Բրանդենբուրգի եպիսկոպոս Բալդերամի գրություններում։ Ըստ վարկածներից մեկի՝ քաղաքն իր անունը ստացել է այդ վայրում բնակություն հաստատած ընտանիքի ազգանունից։ 1302 թվականին կառուցվել է Նաուենի քաղաքապետարանը (ռատուշա), իսկ 1317 թվականին մարկկոմս Վալդեմարը քաղաքին շուկայական առևտրի իրավունք է տվել։ Միջին դարերում քաղաքում բնակություն են հաստատել հրեաներ, իսկ 1800 թվականին սինագոգ է բացվել։
1414 թվականին Նաուենում խոշոր հրդեհ է բռնկվել Դիտրիխ ֆոն Կվիտցովի գործողությունների հետևանքով, իսկ 1631 թվականին ավերվել է Տիլլիի զորքերի կողմից։ 1675 թվականին քաղաքի մատույցներում ճակատամարտ է տեղի ունեցել բրանդենբուրգյան և շվեդական զորքերի միջև, որն ավարտվել է բրանդենբուրգցիների հաղթանակով։
1816 թվականին ձևավորվել է Օստհաֆելլանդի շրջանը, որի կենտրոնը 1826 թ. դարձել է Նաուենը։ Այդ կարգավիճակում քաղաքը մնացել է մինչև 1993 թվականը։ 1846 թվականին Նաուենով անց է կացվել Բեռլին-Համբուրգ երկաթուղին։
1865-1930 թվականներին քաղաքում բազմաթիվ խոշոր նախագծեր են իրականցվել։ Կառուցվել են դպրոց, շաքարի գործարան, նոր քաղաքապետարան, հիվանդանոց։
1912 թվականին Նաուենն էլեկտրաֆիկացվել է, իսկ 1930 թվականին քաղաքի կենտրոնում ջրահեռացման համակարգ է անցկացվել։
1945 թվականի ապրիլի 20-ին ամերիկյան օդուժը ռմբակոծել է Նաուենը, որի հետևանքով 60 մարդ է զոհվել։ Կայարան ու շրջակա շինություններ լուրջ վնասներ են կրել։
1994 թվականի հունվարի 7-ին քաղաքի զինանշան է հաստավել կապույտ կարպ ձուկն արծաթագույն ֆոնին[1]։