A more natural preposition to use in this context would be "for".
"It was very unfortunate for him to have lost the battle."
Using "of" would seem more natural in a sentence such as, "it was very rude of him to have said that". The difference seems to be that being rude is something one does more actively, whereas being unfortunate is something that happens to one. Compare, "that was very kind of him," and "that was lucky for him."
One way to sidestep the problem entirely would be to use a relative clause, with an optional phrase indicating whose misfortune we are concerned with:
"It was very unfortunate (for whomever) that he lost the battle."