(covers information from several alternate timelines)
In the 2170s, the Krenim Imperium was in decline, due to losing a war with the Rilnar. At that time, Annorax was living on Kyana Prime with his wife. Realizing that their war with the Rilnar could not be won by conventional means, Annorax developed a weapon capable of pushing elements (anything from a molecule to a civilization) out of the space-time continuum, thereby creating an alternate timeline where that element never existed. If used against a species, it created a causality paradox in which history changed as a result of the non-existence of that species. With this weapon as the centerpiece, he constructed the Krenim weapon ship, assembled a crew, and set about restoring the Krenim Imperium to its former glory.
The first target eliminated by Annorax was the Rilnar, and initially his weapon achieved spectacular results. However, he had failed to take into account all the consequences of the temporal incursion, one of which was a plague (due to the loss of a crucial antibody that the Rilnar had contributed to the Krenim genome) that devastated the Krenim. To correct this error, Annorax ordered a second incursion, and in doing so accidentally eliminated the colony on Kyana Prime, and with it his beloved wife. A lock of her hair was the only trace Annorax had left.
Stricken by grief, Annorax struggled in vain over the next two centuries to restore Kyana Prime. He oversaw the repeated disappearance and restoration of billions of people over thousands of worlds, but he was never able to accomplish the full restoration of either the Imperium or his wife. From each civilization he removed from history, Annorax collected a sample of their culture to be stored aboard his ship. This included the Malkoth and the Alsurans. As the years passed Annorax came to believe that time itself had "colors" and "moods", and that it was punishing him for his hubris by withholding his wife from him. Therefore, irrespective of his guilt over eliminating so many civilizations, he refused to relent in his mission until he forced time to return his wife to him.
Meanwhile, there was growing frustration and dissent amongst Annorax's crew over their repeated failures and their prolonged separation from their families. This tension escalated dramatically in 2374, when Annorax refused to end their mission after they achieved an unprecedented 98% restoration following the erasure of the Zahl. His reasons were obvious enough: part of the 2% that had not been restored included Kyana Prime. His subsequent incursion, against the Garenor, was a disaster due to the USS Voyager's temporal shields. Annorax was able to abduct Chakotay and Tom Paris to the weapon ship, though Voyager escaped his attempt to erase it from history.
Since he was unable to locate Voyager, Annorax proposed a collaboration to Chakotay and Paris, where they would find a way to use the temporal weapon to aid both the Krenim and Voyager without destroying any additional species. Chakotay was at first sympathetic to Annorax's situation, though he decided to work with Paris to foment a mutiny with Annorax's first officer Obrist, after Annorax eliminated another species, the Ram Izad. Shortly after, Obrist disabled the ship's temporal core during an attack by Voyager and five Mawasi and Nihydron ships. Annorax ordered Voyager to be destroyed, but he was too late as Captain Kathryn Janeway rammed her ship into the weapons ship. But as Annorax witnessed his wife's lock of hair vanish into the mists of time, he suddenly realized that his final goal was about to come true.
The collision destabilized the temporal core, erasing the weapons ship itself from history. This restored the original timeline before Annorax had constructed the ship, reuniting Annorax with his wife on Kyana Prime. In this restored timeline, Annorax decided not to continue his efforts to build the ship, deciding to spend time with his wife instead. (VOY: "Year of Hell", "Year of Hell, Part II")
Background information Edit
Annorax was played by actor Kurtwood Smith who filmed his scenes for "Year of Hell" on Friday 15 August 1997 on Paramount Stage 9 and for "Year of Hell, Part II" between Friday 22 August 1997 and Tuesday 26 August 1997 on Paramount Stage 9 and 16. His uniform from these episodes was later sold off on the It's A Wrap! sale and auction on eBay. 
According to the Star Trek Encyclopedia, Annorax's name comes from the main character in Jules Verne's 20,000 Leagues Under the Sea, Pierre Aronnax, though parallels can be noted with the character of Captain Nemo from the same story, including Tom Paris at one point referring to Annorax as "Captain Nemo".
Since Annorax built the weapons ship two hundred years prior to this episode, the scene of him planning a temporal incursion at end of the episode should have also taken place two hundred years prior. The temporal consequences of this are not clear. Also, since the weapon-ship erased itself from history, it is likely that in the new timeline, the ship will never be built.
In the novel A Pocket Full of Lies, it is revealed that, in the new timeline, Annorax's temporal equations established a strict set of regulations preventing others from manipulating time to the extent that he did in the original course of events, resulting in a Krenim Imperium that is fundamentally more benevolent and reasonable but nevertheless still willing to tamper with history to ensure their supremacy.
In the game Star Trek Online, set in 2410, his technology was used to phase shift the remnants of the Krenim Imperium and hide them from a Vaadwaur invasion fleet. It is revealed that Annorax was able to design the ship, and that records showed what he had tried to do in the events of "Year of Hell". With the aid of the Delta Alliance (the Federation, the Klingon Empire, and the Romulan Republic, as well as their allies in the Delta Quadrant), the Krenim are able to construct a working prototype, christened K.I.S. Annorax after its designer, for use against the Iconians.