Nicolás Storace Arrosa eut son diplôme d'avocat puis de notaire à l'Université de la République de Montevideo, et milita dès sa jeunesse au Parti blanco. Membre de la tendance herreriste du Parti national, il fut nommé ministre de l'Intérieur par le premier Conseil national du gouvernement (à majorité blanca), en 1961, poste qu'il conserva en 1963. Il fut nommé à nouveau à ces fonctions lors du second Conseil national blanco, entre 1965 et 1967. Il eut alors notamment à se confronter à la grève des frigorifiques. Storace était par ailleurs en contact étroit avec la CIA[1],[2].
Storace se présenta en tant que candidat à la vice-présidence aux élections de 1964, en tant que colistier d'Alberto Héber Usher. Cette formule fut néanmoins battue, au sein même du Parti national, par celle menée par Martín R. Echegoyen.