Historical practice strongly influences constitutional interpretation in foreign relations law, including most questions relating to the treaty power. Yet it is strikingly absent from the present debate over whether Congress can pass legislation implementing U.S. treaties under the Necessary and Proper Clause. Drawing on previously unexplored sources, this Article considers the historical roots of Congress’s power to implement U.S. treaties between the Founding Era and the seminal case of Missouri v. Holland in 1920. It shows that time after time, members of Congress understood the Necessary and Proper Clause to provide a constitutional basis for a congressional power to implement treaties. Notably, both supporters and opponents of a strong treaty power accepted Congress’s power to implement treaties under the Necessary and Proper Clause, even though they did so for quite different reasons. This consensus helped lead to the growing practice of treaty non-self-execution, a practice that in turn has led Congress to play an increased role in treaty implementation. The historical practice revealed here strongly supports the conclusion that Congress has the power to pass legislation implementing treaties under the Necessary and Proper Clause, even when no other Article I power underlies this legislation.