Will it? Or do you send two versions of the application to App Store?
It will run, but won't take advantage of the new stuff in iOS4. Otherwise, lots of apps currently in the AppStore that haven't been updated wouldn't work on the new iPhones.
It doesn't really matter any more. Apple is currently only accepting applications and updates built against iOS 4.0 for the App Store:
Make sure that your applications are compatible with iOS 4. All new applications and updates to existing applications must be built with iPhone SDK 4. In addition, the App Store will no longer support applications that target iOS 2.x.
It's my understanding that a 3.x-only application will now be rejected. However, it is trivial to ensure that your 4.0-built application will run on 3.x devices by setting the Deployment Target to 3.0 (or later).