1640s, as a theological term (in reference to "covenants" between God and man), from French fédéral, an adjective formed from Latin foedus (genitive foederis) "covenant, league, treaty, alliance," from PIE *bhoid-es-, suffixed form of root *bheidh- "to trust, confide, persuade."
Secular meaning "pertaining to a covenant or treaty" (1650s) led to political sense of "formed by agreement among independent states" (1707), from use of the word in federal union "union based on a treaty" (popularized during formation of U.S.A. 1776-1787) and like phrases. Also from this period in U.S. history comes the sense "favoring the central government" (1788) and the especial use of the word (as opposed to confederate) to mean a state in which the federal authority is independent of the component parts within its legitimate sphere of action. Used from 1861 in reference to the Northern forces in the American Civil War.