I don't know if the term was used earlier, but the term united States of America (note that "united" is not capitalized) was used in the Declaration of Independence, July 4, 1776:

We, therefore, the Representatives of the united States of America, in General Congress, Assembled, appealing to the Supreme Judge of the world for the rectitude of our intentions, do, in the Name, and by the Authority of the good People of these Colonies, solemnly publish and declare, That these United Colonies are, and of Right ought to be Free and Independent States

It was legally formalized as the name for the country by The Articles of Confederation, the country's "first constitution", a short-lived document which oversaw a much looser confederation of states than what is provided for by our current Constitution.