It was the first major clash of 2007, and possibly the biggest in several months.
The fighting occurred Wednesday night in Paktika province, just across the border from Pakistan.
NATO spokesman Major Dominic Whyte says two large groups of insurgents were observed infiltrating into Afghanistan from Pakistan just before the fighting broke out.
"The insurgents were monitored, tracked and subsequently engaged in Afghanistan through both air and ground fire," he said.
Major White says the operation included both Afghan and international forces.
NATO said initial battlefield assessments suggest as many as 150 insurgents were killed during the fighting. Afghan officials say the death toll may be significantly lower, perhaps around 50 or 60 dead.
The Afghan-Pakistan border itself has been at the center of a growing diplomatic dispute between the two neighbors.
Afghanistan says pro-Taleban insurgents have established a series of sanctuaries inside Pakistan, and are staging deadly cross-border raids with relative impunity.
Islamabad insists it is doing everything it can to help secure the border, including a controversial new plan to fence and mine portions of the ill-defined boundary.
Last year was one of the bloodiest in Afghanistan since 2001, when U.S. forces helped oust the hard-line Taleban regime.
More than 4,000 people were killed during the year, with most of the fighting occurring in those Afghan provinces sharing a border with Pakistan.