The "Time War" (note that the event is more accurately "The Last Great Time War", as there have been at least two others) was introduced in the first episode, Rose, of the 2005 Doctor Who season featuring the 9th Doctor, but the events of the war itself involve earlier incarnations of the Doctor.
In other words, it was introduced by the "new" Doctor Who, but involves the Doctors of the original series and movie.
Doctor Who (the 1996 movie, featuring the 8th Doctor) makes no reference to the "Time War"; however this is not the only storyline featuring the 8th Doctor: there is also a series of books entitled Eighth Doctor Adventures.
The "Time War" is not directly referenced in these, either, but there is a similar (but distinct) plot device (hover for details).
In these books, the Doctor wipes Gallifrey and all but four of the Time Lords from history in order to save them from the Faction Paradox. There are not currently any novels that explain how Gallifrey and the Time Lords are restored before the events of the "Last Great Time War" some time prior to the events of Rose, although the novels do contain an explanation of how this could be achieved. Davies has explicitly said (in Doctor Who Magazine #356) that these are two separate calamities effecting Gallifrey and the Time Lords.
In the audio drama The Apocalypse Element, the 6th Doctor again clashes with the Daleks. Russell T. Davies has said that this may have been an "opening skirmish" of the Time War (in Doctor Who Annual 2006: transcription of dubious legality). This story forms part of the Dalek Empire arc, which include stories about the 5th, 7th and 8th Doctors as well. This production originally aired in 2000, many years after the 5th, 6th, and 7th Doctors ceased appearing in TV episodes, but before the beginning of the episodes featuring the 9th. It is not known whether Davies had these events in mind when he originally developed the Time War, or whether the link is a retcon of sorts.
In the 10th Doctor episode Doomsday, the Doctor states that both the 8th and 9th regenerations fought in the Time War. The reason for the 8th Doctor's regeneration is depicted in Night of the Doctor, where the Doctor decides to become actively involved in the Time War.
More details of the Time Wars and their place in Doctor Who canon can be found on both Wikipedia and the Tardis Index File.