Sheldon graduated from Yale University in 1978 and the University of Virginia Law School in 1982. He served his clerkship under the Honorable Richard F. Neely of the West Virginia Supreme Court of Appeals from 1982-1983.

Sheldon worked in the Rhode Island Attorney General's office as a Special Assistant Attorney General from 1985-1990, Chief of the Regulatory Unit from 1988-1990, and as an Assistant Attorney General from 1989-1990. Sheldon defended the State against civil lawsuits, fought utilities and insurance companies for consumers, and argued cases in the Rhode Island Supreme Court.

In 1991 Sheldon became the Executive Counsel for Governor Sundlun. He was later appointed Director of Policy. Sheldon led the State's response to the credit union collapse and helped repay depositors. Sheldon led the lawsuit that opened up the State's secret pension records to the light of public scrutiny. Sheldon also drafted and won passage of the 1992 Workers' Compensation Reform Act that has saved Rhode Island businesses hundreds of millions of dollars.

In 1992, Governor Sundlun appointed Sheldon as the Director of Business Regulation. Sheldon coordinated the Workers' Compensation reform implementation. Sheldon also created the Auto Theft and Fraud Unit within the Rhode Island State Police, which resulted in a 50% reduction of auto thefts in Rhode Island, and lowered insurance rates.

Sheldon was appointed United States Attorney for the District of Rhode Island in 1994, and he served a 4-year term. During his tenure as United States Attorney, Sheldon prosecuted the Latin Kings, obtained over 750 years in prison sentences for criminals guilty of firearms offenses, secured the first conviction of a member of organized crime under President Clinton's "Three Strikes" law, and obtained over $9 million in criminal penalties for the North Cape/Scandia oil spill.

Sheldon was elected Rhode Island's Attorney General in November of 1998, winning every city and town in the 1998 primary and general elections. Sheldon was sworn into office on January 5, 1999. As Attorney General, Sheldon has focused his efforts on professionalizing the Department, strengthening the Department's prosecution of armed criminals, increasing the Department's role in health care, and expanding the Department's community and crime prevention role. Sheldon personally argued cases before the Rhode Island Supreme Court and the United States Supreme Court.