The unusually strong threat from the secretive communist state comes a day after military officials from the two countries met on the border. At the meeting, the North complained of the continuing barrage of leaflets dispersed from helium balloons launched from the South.
"Should the South Korean puppet authorities continue scattering leaflets and conducting a smear campaign with sheer fabrications, our army will take resolute practical action, as we have already warned," Pyongyang's official Korean Central News Agency cited a military spokesman as saying.
An "advanced pre-emptive strike" would reduce South Korea "to debris", the spokesman said.
The South Korean government stopped official propaganda against the North in 2004, in line with a bilateral agreement. However, while discouraging activists from launching leaflets across the border, the government has refused to take action against them, citing freedom of speech.
Recent leaflets have mentioned Kim Jong-il's deteriorating health, a highly sensitive subject in the North, and have encouraged North Koreans to rise up against the communist regime. On Monday, tens of thousands of leaflets were launched towards the North from a boat.
Relations between the countries have become strained since Lee Myung-bak became South Korea's president earlier this year, taking a tougher stance on the North.
South Korean and U.S. officials say the North Korean leader suffered a stroke earlier this year, and may have undergone brain surgery.
Seoul's Yonhap agency said on Tuesday that a North Korean soldier had defected across the demilitarized zone to the South, only the second such incident in the past 10 years.
The agency cited a military official as saying the North Korean, in his 30s or 40s, crossed the world's most heavily fortified frontier on Sunday. He claimed to be a sergeant and told South Korean guards that he was seeking asylum.