Après avoir tourné intensément pour la promotion de l'album Machine Head, le groupe décide d'enregistrer son prochain album dans un environnement confortable et loue une villa sur la Via Flaminia à Rome[1]. Le groupe y reste trois semaines mais n'enregistre que deux chansons : Woman from Tokyo et Painted Horse. En ce qui concerne ce dernier titre, après avoir travaillé plusieurs jours sur la musique, Ian Gillan pose son chant sur la bande mais Ritchie Blackmore met son veto lorsqu'il entend les paroles. Chacun reste sur ses positions et la chanson ne parut pas sur le disque, ce qui fera de Woman from Tokyo l'unique titre enregistré à Rome figurant sur cet album[1]. Finalement, Painted Horse ne figure que sur l'album d'inédits Powerhouse sorti en 1977 (puis parmi les titres bonus de la réédition de l'album Who Do We Think We Are remastérisé en 2000). Le groupe repart en tournée pour la première fois de sa carrière au Japon (tournée durant laquelle sera enregistré l'album live Made in Japan).
En octobre, l'enregistrement de l'album reprend. Cette fois-ci les musiciens se retrouvent à Waldorf Nord en Allemagne, une petite ville dans les environs de Francfort. Ils résident à Francfort au Park Hotel et ont loué des voitures pour se rendre au studio[1]. Le premier jour, Roger Glover se perd dans les sorties d'autoroute pendant que le reste des musiciens règle le son de leur instruments, ce qui donna une jam impromptue entre Ian Paice (batterie), Jon Lord (claviers) et Ritchie Blackmore qui à cette occasion se saisit de la basse Rickenbacker de Glover[1]. On retrouve aussi cette jam sur la réédition de 2000 sous le titre de First Day Jam. L'écriture des titres et leurs enregistrements se déroulent rapidement, contrairement au séjour italien, mais les tensions grandissent et les musiciens sont rarement ensemble en studio dans le même temps, Ian Gillan et Ritchie Blackmore s'évitant autant que possible[1]. Roger Glover et Ian Paice s'occupent du mixage des sept titres de l'album.
Origine du titre de l'album
À cette époque le groupe reçoit des piles de lettres ; si les unes encensent le groupe, les autres le dénigrent violemment. Ces dernières commencent le plus souvent par "Who do they think they are ?!" (ce qu'on peut traduire par "Mais pour qui se prennent-ils ?!"). C'est Ian Paice qui a l'idée de remplacer le "They" (ils) par "We" (Nous), ce qui donne ironiquement "Who Do We Think We Are" ("Mais pour qui nous nous prenons")[1].
Réception
L'album se classe rapidement aux premières places des charts européens, 4e place au Royaume-Uni, 3e en Allemagne et même la 1re place en Norvège. Aux États-Unis il se classe à la 15e place du Billboard 200 et est certifié disque d'or (500 000 albums vendus). En France il est aussi certifié disque d'or (100 000 albums vendus).