Né dans une ancienne famille samouraï du domaine de Sasayama dans la préfecture de Hyōgo, Andō sort diplômé de la 11e promotion de l'académie de l'armée impériale japonaise en 1899. En 1901, en tant que sous-lieutenant dans l'infanterie, il sert dans la 10e brigade de la garnison de Taïwan. Il est promu lieutenant en 1904, est nommé commandant de compagnie dans le 10e régiment d'infanterie, et est promu capitaine puis major en 1913.
En 1918, Andō est attaché militaire aux États-Unis et est promu lieutenant-colonel durant son séjour. De retour au Japon, il sert dans le bureau du personnel du ministère de la Guerre de 1921 à 1922. En 1922, il est promu colonel, et est affecté à la tête du 73e régiment d'infanterie puis du 2e. De 1923 à 1927, il retourne au bureau du personnel au ministère de la Guerre.
Promu général de brigade en 1927, Andō commande la 30e brigade d'infanterie jusqu'en 1929 puis est affecté à l'État-major de la 1re division de 1929 à 1932.
En 1932, Andō est promu général de division et devient commandant de la forteresse de Ryōjun au Guandong en Chine de 1932 à 1934. Il entre dans la réserve en 1934 mais est rapidement rappelé au service en 1937 au début de la seconde guerre sino-japonaise et est affecté comme commandant de la 9e division de dépôt. Il se retire de nouveau en 1939.
L'année suivante, il est nommé au poste de ministre de l'Intérieur, servant jusqu'à la fin du gouvernement de Tōjō en 1944. À ce poste, il réussit à conserver le commandement de la Yokusan Sonendan, qui est devenu politisée, et qui est de plus en plus critiquée par les politiciens et bureaucrates âgés et commence à se transformer en un mouvement politique populiste indépendant de l'association de soutien à l'autorité impériale[2].