L'origine du nom de la ville remonte dans les années 1600. A cette époque le roi Andrianjaka prend possession des collines de l'Imerina (nom donné à l’ensemble de la région des hautes terres au centre du pays), en chassant les tribus de Vazimba (premiers habitants de l'île issus des premières migrations indonésiennes, auxquels la tradition orale et le folklore populaire prête des pouvoirs malveillants ou bienveillants). Andrianjaka construit le premier Rova (palais) et la fit garder, selon la légende, par 1000 (arivo) hommes. Il donna ainsi le nom d’Antananan’ny arivo (ville des milles) à sa nouvelle place forte. 