Те-Анау тарихы еуропалық колонизацияға дейінгі дәуірден басталады. Жергілікті маорилер, атап айтқанда Нгаи Таху тайпасы, бұл аумақты поунаму (нефрит) іздеу экспедициялары кезінде және азық-түлік дайындау үшін маңызды маусымдық пункт ретінде пайдаланған. Қаланың атауы маоридің «Te Ana-au» сөзінен шыққан, бұл «толқыған суы бар үңгір» деп аударылады, бұл көлдің батыс жағалауындағы үңгірлер туралы аңыздарға сілтеме жасайды.
Еуропалық зерттеушілер көл жағасына алғаш рет 1852 жылы жетті. Қаланы ресми жоспарлау әлдеқайда кеш басталды: жер өлшеушілер болашақ қоныстың аумағын аймақтың әлеуеті айқын болған кезде, 1893 жылы белгіледі. Шалғайдағы аумақтың елді мекенге айналуы Оңтүстік аралдағы ең үлкен көлдің жағасындағы сәтті географиялық орналасуымен байланысты болды, бұл Те-Анауды табиғи көлік торабына және жетуі қиын Фьордленд аймағының қақпасына айналдырды.
Қоныстың қалыптасуында ауыл шаруашылығы маңызды рөл атқарды: XIX ғасырдың ортасында көл айналасындағы кең жазықтар мұнда ірі қой шаруашылығы станцияларын негіздеген фермерлерді қызықтырды. 1888 жылы Квинтин Маккиннонның Милфорд-Саунд фьордына өтетін жолды ашуы бетбұрыс сәт болды, бұл қаланы Тасман теңізінің жағалауымен байланыстырып, жаңа қатынас жолдарын ашты.
XIX ғасырдың аяғы — XX ғасырдың басында Те-Анаудың экономикасы мен мәдениеті қатал фермерлік тұрмыс пен жаңадан басталған туризмнің тоғысында қалыптасты. Ірі орталықтардан алшақ болғандықтан, алғашқы қоныстанушылар өз күштеріне сеніп, өзара көмек көрсету мәдениетін дамытты. Сонымен қатар, сол жылдары Милфорд трек бағыты ашылғаннан кейін қалада алғашқы қонақ үйлер мен гид қызметтері пайда бола бастады, бұл қаланың әлемдік деңгейдегі туристік орталық ретіндегі заманауи мамандануына берік негіз қалады.