Prior to the publication of Del Rey's New Jedi Order series, Bantam Spectra and Dark Horse Comics had been planning their own alien invasion storyline.
There are rumors that Brian Daley and James Luceno developed a plot for an extra-galactic invasion storyline prior to Daley's death in 1996 (and prior to Luceno's involvement in Star Wars). Lucy Wilson first came up with the idea of an extended story-arc spanning more than just a trilogy worth of books in 1997. In March 1998 a Bantam story conference was held at Skywalker Ranch, with a follow-up that May (with Luceno attending both). However, Shelly Shapiro claims no knowledge of any of those events, and Sue Rostoni has stated that none of these events ever took place.
However, The Essential Reader's Companion, published in 2012, does state that a "working outline" by LucasBooks, apparently separate from the Dark Horse storyline, existed in 1998. As of then, the LucasBooks invasion plot would involve Luke Skywalker sending Jacen Solo, Jaina Solo, and Anakin Solo on an "epic quest", during which they would encounter a female infiltrator from an extragalactic species attempting to invade the galaxy. These aliens would be "perhaps the source of the original Sith" who would use the dark side "more out of necessity and for survival than with evil intent." They would have been able to observe the Star Wars galaxy as a beacon of light in the Force for a thousand generations, fearing it as the source of a "light-bringer" who was prophesied to destroy their own civilization. The Great Jedi Purge would have dimmed the galaxy, and they would have decided to invade when the New Jedi Order began to restore its brightness. During the invasion, the female infiltrator would nearly corrupt Anakin to the dark side, but would be redeemed after falling in love with him. However, Jacen and Jaina would still attack Anakin due to "a fit of intense sibling rivalry", resulting in Jacen's death. This version of the outline was scrutinized by George Lucas himself, who rejected the concept of the invaders being dark siders due to his belief that no dark side society could be established, as they would inevitably turn on each other (a concept he would later use in his Sith backstory for The Phantom Menace).
On September 1, 1998, Bantam published Vision of the Future, in which it was revealed that Thrawn had encountered an unimaginable threat to the galaxy within the Unknown Regions. Shortly afterwards, on November 11, Dark Horse began to publish Crimson Empire II: Council of Blood. The authors, Mike Richardson and Randy Stradley, intended it to be a prologue into Dark Horse's planned invasion storyline. The comics story would be told in a series of smaller arcs similar to the later Clone Wars comics.
Shortly after, Del Rey took over from Bantam as the Star Wars book publishers, and Lucasfilm canceled the Crimson Empire III comic, which was expected to continue the run-up to their invasion. Del Rey and Dark Horse representatives met to discuss their respective invasion ideas, and the majority of the storyline was given to Del Rey, who took it in directions that Dark Horse did not intend. Stradley stated that following the decision, the team at Dark Horse Comics was "pretty soured" about releasing material set during the New Jedi Order era. A comic prologue to the New Jedi Order entitled The Hatred Vector was never produced. The tie-in Chewbacca comic and "Equals & Opposites," however, were subsequently published by Dark Horse.
In 2009, six years after the conclusion of Del Rey's New Jedi Order series, it was revealed at the New York Comic Conference that Dark Horse Comics would be releasing Star Wars: Invasion, a comic series set contemporaneously with The New Jedi Order series. In subsequent interviews following the initial press release, Stradley elaborated on the previous decisions made by Del Rey and Dark Horse Comics. Stradley stated that the idea of a comic series set during the events of The New Jedi Order had remained a point of discussion, among other concepts, since 2002. Eventually, the decision was made that the Rise of the Empire era and the Rebellion era were constricting in terms of continuity and that releasing a comic series in the New Jedi Order era would allow the Dark Horse Comics team to focus on a grand galactic event that was not subject to frequent continuity changes and in which there was still a significant amount of "uncharted territory".
The storyline shared some elements with what eventually became the New Jedi Order:
- Chewbacca would have died early on in the story.
- Nom Anor would have been an advance scout of the aliens.
- Thrawn's Unknown Regions threat would likely have been retconned into being the invasion.
- The invaders would have been armed with a type of bladed weapon that would have allowed them to fight Jedi; this possibly became the amphistaff.
- The invaders would have been led by a "god-king and his dwarfish adjutant" who existed in a symbiotic relationship, with the adjutant being killed by the surviving Solo son. These characters were the basis for Shimrra Jamaane and Onimi.
However, other elements were different: