The evolution was actually Vampires to Fallen Angel to Dystopian. I think you're thinking that Paranormal Romance is hot right now, but it's simply because now there is so much of it available because of the previous glut, and you also have all those authors who did well in the genre continuing to write in it. But as far as what is actually hot, it's not that. Agents/Editors are getting a bit tired of it. And right now it's all dystopian all the time.
To answer the question of what came before Vampires. Nothing. Aside from Harry Potter. Harry Potter changed the nature of the children's book industry. TWILIGHT the nature of the YA book market. Before them, both were small, and far less trendy. Remember, the concept of books for younger people being a major source of income for publishers only started when Harry Potter took off. Before that it was a much smaller market. Further the concept of YA is I'd venture to suggest only a decade old. There has always been books for young people out there, but before recently they were read by pre-teens, not teens. This is the first time that we have books for YAs read by YAs. I wrote a blog post on the subject
here.
