The Rainbow Children era, 2001/2. This was one of a couple of nights on The Tonight Show. He was performing "The Ballad of Dorothy Parker" with some Madhouse thrown in. (Maybe "Four"? I forget off hand.)

Check PrinceVault to find the dates. He also performed "The Work" on another night.

7salles said:

On youtube we can find a video called: Michael Jackson vs Prince #3 keyboards. On this small video there is a wonderful piano solo by Prince. Question is: from what concert was that performance from? Prince was with a black suit and hat and a long hair from what i can tell. The drummer is blackwell. But i cant recall a period that prince had long hair with a late incarnation of npg. I need to see that concert because his keys chops were on fire!

As it says in the video - it was on the Tonight Show (with Jay Leno). Back in 2001.