Le Dictionnaire historique de la langue française (sld Alain Rey) signale l’apparition de la locution adverbiale de nouveau (de nuvel) en 1121-1134,

« d’abord avec le sens de « récemment, depuis peu » qui a disparu,
puis avec la valeur moderne de « une fois de plus » (1160). La
locution à nouveau (1135) est d’abord employée spécialement
comme terme de banque au sens de « sur un nouveau compte » et se
distingue de de nouveau en ce qu’elle signifie « une fois de plus,
mais avec une façon différente » (1852). Cependant cette nuance n’est
pas toujours sentie par le locuteur, qui lui donne souvent le sens
« d’une fois de plus » (1884).