He spoke of recent U.S. military strikes in Syria and Afghanistan as evidence of President Trump's "strength and resolve."
The warning came as Pence visited South Korea at the start of a four-nation Asia trip. He spoke during a joint appearance in Seoul with South Korea's acting president, Hwang Kyo-ahn.
Pence urged the U.S. to move away from a previous policy of what he called "strategic patience." He said this policy had failed to produce lasting progress with North Korea.
"For more than two decades, the United States and our allies have worked to peacefully dismantle North Korea's nuclear program, and alleviate the suffering of their people. But at every step of the way, North Korea answered our overtures with willful deception, broken promises and nuclear and missile tests."
Pence noted that during the past 18 months, North Korea had carried out two nuclear tests and more missile tests than ever before.
Kim Jong Un's government conducted its latest missile test on Sunday, just before Pence's arrival. The test failed when the missile exploded shortly after launch.
Stopping a North Korean nuclear missile
While Vice President Pence is in Asia, he is expected to seek support for increasing pressure on North Korea to end its nuclear and missile development programs.
"All options are on the table," Pence told reporters at the Demilitarized Zone (DMZ) that separates North and South Korea.
However, U.S. National Security Adviser H.R. McMaster said he is not currently considering a military option. On a TV news program, McMaster said U.S. officials are aiming to contain the threat peacefully.
The Trump administration is reportedly considering new economic restrictions on North Korea. These could include an oil embargo, a global ban on its airline, stopping cargo ships, and punishing Chinese banks that do business with North Korean companies.
Other players in the area
China remains an important partner for the U.S. on North Korea. But Chinese officials have not supported strong measures against North Korea, which is a close ally of China. Those measures could cause instability at China's border and increase U.S. power in the area.
A Chinese Foreign Ministry spokesman called for restarting multi-party talks that ended without agreement in 2009. He also spoke out against deploying the THAAD missile defense system in South Korea. Both Pence and Hwang repeated their support for THAAD as a way to protect against North Korean missile strikes.
In Tokyo, Japanese Prime Minister Shinzo Abe said a "diplomatic effort is important to maintain peace" on the Korean Peninsula. But he said "dialogue for the sake of having dialogue" is useless.
"We need to apply pressure on North Korea so they seriously respond to a dialogue," Abe told a parliamentary meeting. He urged the international community, especially China and Russia, to play a bigger role in the issue.
I'm Bryan Lynn.