In 1996 Eaves ran for the U.S. House of Representatives seat from Mississippi's 3rd congressional district. Defeating two other candidates in the Democratic primary, he faced former U.S. Senate aide Chip Pickering in the general election. Pickering won with 61 percent of the vote.
