We just went to the library and visited the history section and looked up history stuff in the catalog and checked out a bunch of stuff. My son, then 4 1/2, would read some of it and reject some of it. He's always loved history documentaries as well. When he was 7, we stopped at the video store to let him pick out a movie - a treat. He chose "The War in Iraq" by the History Channel. He loved it. So, I agree with the above, expose him to a lot of stuff and let him pick what he's interested in.
Later, the Time Warp Trio series are good - you choose how the story goes by answering questions at different points. I'm thinking they were all historical fiction but I can't quite remember.
