The U.S. Pacific Command said it was assessing the type of missile but it was "not consistent with an intercontinental ballistic missile", Japanese Defense Minister Tomomi Inada said the missile could be of a new type.
The missile flew 700 km (430 miles) and reached an altitude of more than 2,000 km (1,245 miles), according to officials in South Korea and Japan, further and higher than an intermediate-range missile North Korea successfully tested in February from the same region of Kusong, northwest of its capital, Pyongyang.
North Korea is widely believed to be developing an intercontinental missile tipped with a nuclear weapon that is capable of reaching the United States. U.S. President Donald Trump has vowed not to let that happen.
Experts said Sunday's test showed a considerably longer range than missiles North Korea had previously tested, meaning it had likely made improvements since its February test.
The reported altitude would indicate the missile was launched at a high trajectory.
David Wright, co-director of the UCS Global Security Program and a missile expert, said if the missile had been fired at a standard trajectory, it would have had a maximum range of about 4,500 km (2,800 miles).
Kim Dong-yub, Kyungnam University's Institute of Far Eastern Studies in Seoul, said he estimated a standard trajectory firing would give it a range of 6,000 km (3,700 miles), meaning it would be capable of reaching Hawaii.
An intercontinental ballistic missile is considered to have a range of more than 6,000 km.
Japan said the missile flew for 30 minutes before dropping into the sea between North Korea's east coast and Japan. The North has consistently test-fired missiles in that direction.
"If that report ... is correct, then the launch may indeed represent a new missile with a long range," said Jonathan McDowell of the Harvard Smithsonian Center for Astrophysics, referring the estimated altitude of more than 2,000 km.
"It is definitely concerning," McDowell said.
In Washington, the White House said Trump "cannot imagine Russia is pleased" with the test as the missile landed closer to Russia than to Japan.
"With the missile impacting so close to Russian soil – in fact, closer to Russia than to Japan – the President cannot imagine that Russia is pleased," it said.
The launch served as a call for all nations to implement stronger sanctions against North Korea, it added.
The launch, at 5:27 a.m. Seoul time (2027 GMT Saturday), came two weeks after North Korea fired a missile that disintegrated minutes into flight, marking its fourth consecutive failure since March.
South Korean President Moon Jae-in, who took office on Wednesday, held his first National Security Council in response to the launch, which he called a "clear violation" of U.N. Security Council resolutions, his office said.
"The president said while South Korea remains open to the possibility of dialogue with North Korea, it is only possible when the North shows a change in attitude," Yoon Young-chan, Moon's press secretary, told a briefing.
Moon won Tuesday's election on a platform of a moderate approach to North Korea and has said he would be willing to go to Pyongyang under the right circumstances, arguing dialogue must be used in parallel with sanctions.
The launch will also complicate Moon’s efforts to mend ties with China that have been strained by a decision by South Korea's former government to deploy a U.S. anti-missile defense system aimed at defending against North Korea.
Despite South Korean and U.S. assurances that the deployment is defensive, China considers the system's powerful radar a threat to its security.
In a telephone conversation with Chinese President Xi Jinping last week, Moon said while he understood China’s concern, it would be difficult to resolve the issue unless North Korea stopped being provocative.
Japanese Prime Minister Shinzo Abe said North Korea's repeated missile launches were a "grave threat to our country and a clear violation of UN resolutions".
Abe said the foreign ministers of Japan and South Korea had spoken after the firing, and his top security adviser had a call with U.S. national security adviser H.R. McMaster.
There was no immediate reaction from China.
Delegations from the United States, South Korea and North Korea are in Beijing for a conference on a plan for a new Silk Road. Russia's President Vladimir Putin is also there.
Talking about talks
North Korea on Feb. 12, launched the Pukguksong-2 missile, an upgraded, extended-range version of its submarine-launched ballistic missile, from the same site.
South Korean and U.S. military officials said the February launch was a significant development as it successfully tested a solid-fuel engine from a mobile launcher. The missile flew about 500 km with an altitude of 550 km.
It represented a more significant threat because of the difficulty of tracking a mobile launcher and because of the ability to keep the missile fueled in advance, unlike liquid fuel rockets.
The North attempted but failed to test-launch ballistic missiles four consecutive times in the past two months but has conducted a variety of missile tests since the beginning of last year at an unprecedented pace. It also conducted its fourth and fifth nuclear tests since then.
Trump warned in an interview with Reuters in April that a "major, major conflict" with the North was possible, but he would prefer a diplomatic outcome.
Trump has also said he would be “honored” to meet North Korean leader Kim Jong Un under the right circumstances.
On Saturday, a top North Korean diplomat said it was open to dialogue with the Trump administration under the right conditions, without elaborating.
The diplomat, Choe Son Hui, spoke to reporters in Beijing after a conference with former U.S. officials in Norway.