"It's a petty decision," he told Spanish television, explaining he had gone to Iran in 2013 to attend President Hassan Rohani's swearing-in ceremony.
"I went as a representative for all those who negotiated" a deal later reached in 2015 aimed at ensuring Tehran would not develop a nuclear bomb, from which the United States withdrew in May.
"People must go to the most complicated countries to keep going with negotiations.
"What seems most shocking to me is that these people be treated the same way as others" in terms of being allowed or denied entry.
The online entry application has to be filled in by EU residents before a trip to the United States of three months or less.
But since 2015, people having previously travelled to Iran, Iraq, Syria, Sudan, Libya, Somalia or Yemen can no longer get this fast-track authorisation and have to apply for a visa.
The restriction doesn't normally apply to government employees, but Solana was not in such a post in 2013.
"What they have (in the United States) is a computer with an algorithm, and if it knows that you went to Iran recently, it takes you off the system," he said.
"I'm going to try and make sure they let me go over, I need to go as I work there, I'm a professor in several universities."
The Spaniard headed up the NATO military alliance from 1995 to 1999 and subsequently became EU foreign policy chief until 2009.