Edmund was a member of the prominent Randolph family in Virginia. His father was the king's attorney John Randolph and his uncle was Virginia politician Peyton Randolph. He studied law as a young man and joined the Continental Army during the American Revolution. He was elected to the Continental Congress from 1779 to 1782. He was elected governor of Virginia in 1786.
The following year, as a delegate from Virginia to the Constitutional Convention, Randolph introduced the Virginia Plan as an outline for a new national government. Randolph refused to sign the final document, however, believing it had insufficient checks and balances, and published an account of his objections in October 1787.
Randolph was appointed as the first U.S. Attorney General in September 1789, maintaining precarious neutrality in the feud between Thomas Jefferson and Alexander Hamilton. When Jefferson resigned as Secretary of State in 1793, Randolph succeeded him to the position.