Salehi, who is in the Belgian capital of Brussels to attend the third seminar on peaceful nuclear cooperation, made the remarks in an interview with Reuters on Tuesday ahead of a meeting with EU foreign policy chief Federica Mogherini in Brussels.
He said the EU's efforts were encouraging but added: "We have not yet seen any tangible results."
"So, they [Europeans] are promising us that they are doing their best to be able to translate all that they have said in political terms and to turn it into realization, in other words, to materialize what they have said," Salehi said.
"So, we wait and see. But I will pass certainly a word of caution to her (Mogherini) that I think the period of patience for our people is getting more limited and limited," he added.
"We are running out of the assumed timeline, which was in terms of months."
US President Donald Trump withdrew his country in May from the multilateral nuclear agreement, officially known as the Joint Comprehensive Plan of Action (JCPOA), and decided to re-impose unilateral sanctions against Tehran, Presstv reported.
Under the deal, reached between Iran and six major powers - the United States, Britain, France, Germany, Russia and China - Tehran agreed to put limits on its nuclear program in exchange for the removal of nuclear-related sanctions.
Earlier this month, the Trump administration announced the re-imposition of the “toughest” sanctions ever against Iran's banking and energy sectors with the aim of cutting off the country's oil sales and crucial exports.
A first round of American sanctions took effect in August, targeting Iran's access to the US dollar, metals trading, coal, industrial software, and auto sector.
The US administration hoped to get the other parties to the deal with Iran to likewise scrap the deal, but instead, they stressed that not only would they stick to the agreement, but they would also work to sustain it in the face of increased US pressure. Europeans believe that the nuclear deal is an important element of international security.
The Iranian nuclear chief further warned that Tehran has the technical capacity to resume its 20 percent uranium enrichment if it fails to enjoy the economic benefit of the JCPOA.
"It is very easy for us to go back to what we were before - even to a better position," he said. "We can start the 20 percent enrichment activity. We can increase the amount of the enriched uranium."
Salehi noted that Iran is currently limited to 300 kilograms enriched uranium but can increase the amount, adding, "And so, there are so many other things we can do, but I wish that we never reach that stage."
Under the 2015 nuclear agreement, Iran stopped producing 20 percent enriched uranium and gave up the majority of its stockpile.
Elsewhere in the interview, the AEOI head said Iran welcomes EU efforts to establish a special financial vehicle for non-dollar trade with Tehran but only if it could preserve the country's oil exports.
Europe has been taking a range of measures to meet the Iranian demand for practical guarantees. Iran and the European side have been discussing ways to conduct non-dollar trade in order to offset the US sanctions.
On September 24, Iran and its five partners released a joint statement announcing the setting up of a Special Purpose Vehicle (SPV) to facilitate continued trade with Iran, bypass the US financial system, and avoid any impact of America's secondary sanctions.
"It (the SPV) could be helpful in keeping the deal alive. If there is nothing to reap then what is the purpose of us staying in because voices in Iran are day by day becoming more against the deal," Salehi said.
"If we cannot sell our oil and we don't enjoy financial transactions, then I don't think keeping the deal will benefit us anymore," he pointed out.
Addressing the nuclear cooperation seminar on Monday, Salehi criticized the US administration's efforts to prevent the implementation of the historic nuclear agreement through exerting pressure on other countries to make them pursue Washington's policies vis-a-vis the deal.
"This unconstructive US approach shows that this country, as a permanent member of the [United Nations] Security Council, is not committed to its international obligations," the AEOI head said.
Salehi and Mogherini are expected to meet on Tuesday afternoon, with no media statements expected afterwards.