Randolph was born at Tazewell Hall to the prominent colonial Randolph family in Williamsburg, Virginia, and he was educated in law at the College of William and Mary. After graduation he began practicing law with his father John Randolph's firm. In 1775, with the start of the American Revolution, most of the Randolph family, largely Loyalists, returned to Britain; Edmund Randolph, on the contrary, joined the Continental Army as aide-de-camp to General George Washington.
Upon the death of his uncle Peyton Randolph he went to Virginia to act as executor of the estate, and while there was elected as a representative to the state constitutional convention. He would go on to serve as mayor of Williamsburg, and then as the first attorney general of Virginia under the newly-formed state government.
Randolph was selected as a delegate to the Continental Congress in 1779, and served there to 1782. During this period he also remained in private law practice, handling numerous legal issues for George Washington among others.
Randolph was elected Governor of Virginia in 1786, that same year leading a delegation to the Annapolis convention where he introduced the Virginia Plan. Later as a delegate to the Constitutional Convention he argued against importation of slaves and in favor of a strong central government, advocating a plan for three chief executives from various parts of the country. He was also a member of the "committee on detail" which was tasked with drawing up the final version of the Constitution. Randolph, however, refused to sign the final document, believing the form of government it would engender had insufficient checks and balances, and published an account of his objections in October of 1787. He nevertheless urged its ratification in 1788, seeing its adoption as necessary at that point.
He was appointed U.S. Attorney General in September 1789, maintaining a precarious neutrality in the feud between Thomas Jefferson (of whom Randolph was a distant relative) and Alexander Hamilton. When Jefferson resigned as Secretary of State in 1793, Randolph succeeded him to the position. In this post he held a similar strict neutrality between the interests of France and Great Britain, earning the scorn of both in the process.
Randolph set forth the guidelines for John Jay's mission to London in 1794; these were, however, ignored; the resulting Jay's Treaty left Randolph to mollify both France and the Federalists; in this he was largely unsuccessful.
Near the end of his term as Secretary of State negotiations for Pinckney's Treaty were finalized.
A scandal involving an intercepted French message implying Randolph was prone to bribery led to his resignation August 1795, although the allegations were provably unfounded.
After leaving the cabinet he returned to Virginia to practice law; his most famous case was that of defense counsel during Aaron Burr's trial for treason in 1807.
Randolph died at his home, Carter Hall, near Millwood, Virginia in Clarke County.