Carrie:

That's exactly how it works, and the only way it works.  Remember that the US is a federal system with two pertinent tiers of laws -- state and federal. 

Organizations are created under state law, not under federal law (with extremely rare exceptions).  Federal tax exemption is handled (by definition) at the federal level.  A not-for-profit organization must first incorporate under state law, and then proceed to seek a federal tax exemption as a non-profit under 501(c)(3) (or other relevant subsections for particular types of organizations). 

In other words, an organization cannot apply for federal tax exemption under 501(c)(3) until it has incorporated as a non-profit under the law of a state of the U.S. [While there are organizations other than corporations that may qualify for federal tax exemptions, such as trusts and "community chests," they are not relevant to this discussion.]