What were the first signs that Virginia was trending leftward?

[Nyssus]

Dole's 2% margin in the 1996 election.

[Smash255]

Started showing signs in 2000, and by 2004 it was pretty evident.  Fairfax trended 20 points Dem compared to the national average between 1996 and 2004.  Loudoun, Prince William and Henrico were all into the double digits as well

[Chips]

Jim Webb's victory in 2006 made me more open to thinking Virginia would be competitive in future elections.

Clinton doing quite a bit better in Virginia than the nation in 2016 and all statewide Democrats winning by solid margins in 2017 made me realize that Virginia was unlikely to go to the GOP in the near future, at least not on the federal level.

[Interlocutor is just not there yet]

To me, 2004 would have been the obvious wakeup call due to Bush's loss of Fairfax County.  Clinton's strength in VA was largely due to strength in rural Western Virginia and the Southeast, with NoVA being solidly Republican at the time.  2001 is possible, but again, this was very much the "Old Virginia Democrat" coalition - Warner was very strong all across rural Virginia, and despite winning Fairfax, it wasn't instrumental to his win.  Also there was a tradition of the opposite party of the White House winning in off years, so this shouldn't be a huge surprise.  2004, on the other hand, showed a sharp shift of the NoVA suburbs away from Bush and the state barely voting more Republican than the country as a whole, a novel situation. 

Yeah, the Fairfax curb-stomping in 2004 shoulda been the big warning sign, just like I suspect Gwinnet and Cobb Counties in 2016 will be looked at as the big warning signs for Georgia when it inevitably goes Democratic in either 2020 or 2024.

Unless Trump goes to below 30 approval then maybe 2024 and even then it will be tight. Even though Georgia is suburban it needs more time for the suburban areas to be able to counter the deeply conservative rural areas.

[Non Swing Voter]

There were clear signs of NOVA trending in 2004.  And around that time it was also clear that NOVA was growing much faster than the rest of the state.