The word entered common use in eighteenth century England, where an expanding number of Protestant groups needed a way to describe each other without conceding that only one of them was the true church. Earlier centuries had used sect, a term that carried the accusation of deviance built into it. Denomination did the opposite work: it named a group by what it called itself, and left the question of ultimate legitimacy alone.
The shift followed the Act of Toleration of 1689, which let dissenting Protestants worship legally in England without joining the established Church of England, and it accelerated as Methodism grew from a renewal movement inside that church into a separate body after John Wesley's death, formalizing its independence in 1795. The same vocabulary took hold even faster in the American colonies and then the United States, where the First Amendment of 1791 barred an establishment of religion outright.
With no state church to defer to, Baptists, Presbyterians, Congregationalists, Episcopalians and a growing list of others had no choice but to coexist as denominations, each a complete church in its own eyes and a partial one in the wider count. The sociologist Ernst Troeltsch and his successors later built a three part typology of church, sect and denomination out of this history, treating the denomination as the form a sect takes once it stops expecting the wider society to convert and settles into permanent, respectable coexistence with its rivals.