Can he simply sign an executive order withdrawing from the founding treaty? If not what would the procedure be?
If the treaty itself contains provisions for how a member nation can leave, then we can follow those procedures, though I doubt an executive order would be sufficient.
If the treaty does not contain such provision, then we might be able to negotiate a new treaty with all of the other member nations to withdraw.
Short of that, there’s no way out. Under the Constitution, treaties share equal status as the supreme law of the land.
Apparently, the answer is maybe. 
Bush did terminate the ABM Treaty without any sort of congressional approval.
But I glossed over the heart of the question: the North Atlantic Treaty does allow countries to leave.
How does either the President, or the President together with Congress, have the authority to change the supreme law of the land?
OK, Ravenman got in there before my post. That seems straightforward enough… but who in each Party has the authority to make such communication?
And of course, if the US does withdraw, what’s the status for anyone else to withdraw thereafter? Are they expected to give notice to a non-member nation? Does the US have any obligation to forward such notice to the other nations? Does the US have special status in any other portions of the treaty, and if so, what happens to those parts?
Each country has its own process for powers relating to treaties. The law of treaties gives great deference to how each country deals with treaty law, so this question will have different answers depending on the country.
The remaining countries would probably just work out a new process. It isn’t like treaties are written in stone and can’t be amended.
As John Mace noted, it’s a complicated issue. The Constitution requires the consent of the President and two-thirds of the Senate to enter a treaty. But it does not say whose consent is needed to leave a treaty.
Well, according to the Constitution itself “This Constitution, and the Laws of the United States which shall be made in Pursuance thereof; and all Treaties made, or which shall be made, under the Authority of the United States, shall be the supreme Law of the Land” (Article 6, Clause 2). And obviously Congress (and the President, or a super-majority of Congress if the President chooses to veto legislation) can change “the Laws of the United States”; heck, that’s pretty much their job. And the POTUS and two-thirds of the Senate can together change “the supreme Law of the Land” by ratifying new treaties.
Neither federal laws nor treaties can override the Constitution itself; the “Constitution, the Laws of the United States which shall be made in Pursuance thereof [that is, in accordance with the provisions of the Constitution and its amendments – MEB]; and all Treaties made, or which shall be made, under the Authority of the United States, [again, treaties can only be made within the limits of the Constitution itself – MEB] shall be the supreme Law of the Land”.
So the “supreme Law of the Land” is the Constitution; under the authority of the Constitution, and within the limits on the power of government in general and the federal government in particular which the Constitution sets in place, the President and Congress then pass federal law and negotiate and ratify treaties. (And federal law in turn often gives authority to create federal regulations, and there are also executive orders and so forth.) Those federal laws and treaties are in turn part of the “supreme Law of the Land”; a state can’t withdraw from NATO or the UN or something like that.
The only other section of the treaty that gives the United States a special status is essentially the opposite of the withdrawal section: if a new country joins NATO it does so by informing the United States government. In both cases, the United States government is obligated to inform the other NATO countries.
AFAIK, treaties are equal in status to acts of Congress, so an act of Congress completely nullifying the treaty would, as a more recent enactment, take precedence over the treaty in domestic law.
If they couldn’t there really wouldn’t be much point in them turning up for work.
Yes, if (and I think this is very unlikely to actually happen) the US did full withdraw from NATO then I think it’s likely the remaining issues would scrap it and form an entirely new treaty amongst the remaining members. It would also quite possibly accelerate the formation of an EU Defense Force. Yes France and the UK might go their own way, but the remaining EU members are going to realise they are much safer with joint defense than otherwise.
Now you know what we’re going through with activating Brexit!
From everything I can see, the answer to this is sort of yes, and sort of no. Mostly no, for mechanical reasons.
NATO isn’t just a conceptual agreement, where everyone goes about their business until there’s a war, and then either shows up or not. An executive order that ended something so complex, would have to direct all sorts of people to perform a lot of tasks, including either withdrawing a lot of military forces from all over the world, or negotiating entirely new replacement agreements in order to deal with the mechanisms of NATO.
I read that nice link to the saga of the ABM treaty withdrawal, and that describes how it wasn’t a simple matter of Bush saying “okay, we’re out.” A LOT of consultations, activities, realignments, and coordinations were involved.
As with many things, the Constitution doesn't spell things out directly or clearly, so there doesn't appear to be a simple answer, even to exactly what a President can do with an EO in this case.
We know from Trump’s first Ban on immigration EO, that the courts CAN say no to an EO.
In civilian commercial life, individuals can sign “treaties” (agreements) with each other and with companies, and then unilaterally withdraw from them, but there are consequences. Those consequences vary, but most don’t include incarceration. Withdrawing or otherwise negating an existing international treaty also has consequences, which are not always written into the treaty.
Regarding the highlighted bit in your quote… the courts intervened because plaintiffs alleged harm caused by the executive order, and the courts accepted that they had appropriate standing.
Who would have standing in matters of international military policy? J. Random Taxpayer can’t successfully sue just because they don’t agree with the policy change. They have to demonstrate some likelihood of particular harm to themselves, to the satisfaction of the appropriate court.
IANAL, it just seems that matters of international relations are too distant from day-to-day life that no individual or group would be able to take them to court.
Congress can certainly change the ordinary law of the land. But the Constitution and treaties are both supreme. To be supreme, they must be over something, which presumably means they’re over the ordinary laws Congress can pass.
Once again:
The “ordinary law” that Congress can change is also part of the “supreme Law of the Land”. There is absolutely no distinction in terms of “supreme-ness” made here between “the Laws of the United States” and “all Treaties made, or which shall be made”.
The Supremacy Clause means that the Constitution, treaties and acts of Congress trump state law, not “ordinary laws.” All acts of Congress are “laws made in pursuance thereof.” They also trump federal administrative law, but that wasn’t really a thing at the time the framers were working.
I’m not all that sure of that. Eastern Europe is where NATO really matters (at least as currently conceived). Of the 17 Eastern European NATO members, it has majority support in seven of them, and in the other 10 most people tend to be apathetic about it.