Le jeu raconte un chapitre non visité d’Assassins Creed II (chronologiquement, il semblerait que l'histoire soit comprise entre les évènements de l'épisode sur console de salon puisque ce dernier couvre une large partie de la vie du héros, soit 30 ans) : Ezio Auditore da Firenze voyage jusqu'en Espagne (Barcelone, Saragosse, Grenade, Alhambra) afin de sauver ses camarades Assassins menacés par l'Inquisition. Il y découvre un complot des templiers manigançant d'aller à l'Ouest, vers le Nouveau Monde.