Under the name NK Vukovar '91, club was founded in Zagreb by Vukovar refugees during the Croatian War of Independence. In 1992, newly founded Vukovar '91 merged with NK Sloga, traditional Vukovar football club.
In the 2001–02 season, they finished first in the North Division of Druga HNL but were defeated by Šibenik in two-legged promotion play-off. In 2007–08 season they were relegated from Druga HNL, but managed to come back after just one season in the third tier of Croatian football. Their third spell in Druga HNL did not last long and they were relegated once again at the end of 2010–11 season.
In January 2012, the club stepped out from Treća HNL East due to financial difficulties. On 8 February 2012, it was announced that the club was officially dissolved due to high debts. In the summer of 2012, a new club under the name HNK Vukovar 1991 was formed.