On May 29, 1787, the first day of substantive debate at the Constitutional Convention, it fell to Randolph to present Madison's framework. The Commerce Clause was there from the start.
Madison's convention notes on Randolph's presentation recount him saying that "there were many advantages, which the U.S. might acquire, which were not attainable under the confederation -- such as a productive impost [or tax] -- counteraction of the commercial regulations of other nations -- pushing of commerce ad libitum -- &c &c."
In other words, the Founders -- at their most "originalist" moment -- understood the value of the federal government taking action to negate the commercial advantages of other countries and to take steps for "pushing of [American] commerce." The "ad libitum -- &c &c" notation suggests that Randolph provided other examples off the top of his head.
Historian Bill Chapman has summarized Randolph's point as saying "we needed a government that could co-ordinate commerce in order to compete effectively with other nations."
So, from the very start of the debate on a new Constitution, Madison and other key Framers recognized that a legitimate role of the U.S. Congress was to ensure that the nation could match up against other countries economically and could address problems impeding the nation's economic strength and welfare.
This pragmatism imbued Madison's overall structure even as he included intricate checks and balances to prevent any one branch of government from growing too dominant. The final product also reflected compromises between the large and small states and between Northern and Southern states over slavery, but Madison's Commerce Clause survived as one of the Constitution's most important features.
However, the Constitution's dramatic transfer of power from the states to the central government provoked a furious reaction from supporters of states' rights. The Articles' phrasing about state "sovereignty" and "independence" had been removed entirely, replaced with language making federal law supreme.
The Anti-Federalists recognized what had happened. As dissidents from the Pennsylvania delegation wrote: "We dissent " because the powers vested in Congress by this constitution, must necessarily annihilate and absorb the legislative, executive, and judicial powers of the several states, and produce from their ruins one consolidated government."
As resistance to Madison's federal power-grab spread -- and as states elected delegates to ratifying conventions -- Madison feared that his constitutional masterwork would go down to defeat or be subjected to a second convention that might remove important federal powers like the Commerce Clause.
So, Madison -- along with Alexander Hamilton and John Jay -- began a series of essays, called the Federalist Papers, designed to counter the fierce attacks by the Anti-Federalists against the broad assertion of federal power in the Constitution.
Madison's strategy was essentially to insist that the drastic changes contained in the Constitution were not all that drastic, an approach he took both as a delegate to the Virginia ratifying convention and in the Federalist Papers. But Madison also touted the advantages of the Constitution and especially the Commerce Clause.
For instance, in Federalist Paper No. 14, Madison envisioned major construction projects under the powers granted by the Commerce Clause.
"[T]he union will be daily facilitated by new improvements," Madison wrote...
"Roads will everywhere be shortened, and kept in better order; accommodations for travelers will be multiplied and meliorated; an interior navigation on our eastern side will be opened throughout, or nearly throughout the whole extent of the Thirteen States.
"The communication between the western and Atlantic districts, and between different parts of each, will be rendered more and more easy by those numerous canals with which the beneficence of nature has intersected our country, and which art finds it so little difficult to connect and complete."
While ignoring Federalist Paper No. 14, today's right-wingers are fond of noting Madison's Federalist Paper No. 45, in which he tries to play down how radical a transformation, from state to federal power, he had engineered in the Constitution.