Cornyn, who is running for re-election in 2008, gave a legislative update to about 100 business leaders and local officials at the Greater El Paso Chamber of Commerce.
The senator spoke about his support of the war in Iraq, the need for a bigger U.S. Army and Congress' low approval ratings, but the meeting quickly focused on border security.
"Fixing immigration is the single most important domestic challenge. But we've done it before. In 1986, amnesty came but enforcement didn't," Cornyn said. "We need to at least double the size of the Border Patrol. There are 10,000 Border Patrol agents. There are 40,000 police officers in New York City, but one fourth of that along a 2,000-mile border."
Such a stand is not overwhelmingly popular on the border where a daily cross-border back-and-forth is essential to business interests.
Indeed, the only room-wide applause during Cornyn's speech came after he said that increasing border security "would not entail a 2,000-mile wall on the border."
Last month, Cornyn voted for a $3 billion measure to build 700 miles of fence and 300 miles of vehicle barriers and to beef up the Border Patrol.
Cornyn, who had spoken against border fencing in the past, said in an interview Monday that he had not changed his mind, but that "in some places, urban areas where it's simply possible to come across and get lost in the city, some fencing is possible."