The last-minute decision - announced shortly before he hopped on a plane - set up a confrontation between Pompeo and European diplomats who have been scrambling to save the deal.
Iranian leaders announced last week they would scale back their cooperation under the agreement, in essence forcing Europe to choose between defying Washington or kissing goodbye to the 2015 deal. Europe sees it as key to preventing a nuclear-armed Iran.
Pompeo scrapped a day of mostly ceremonial events in Moscow on Monday in favor of the Brussels stopover. He plans to meet Russian President Vladimir Putin and Russian Foreign Minister Sergei Lavrov in the Black Sea resort of Sochi on Tuesday. Many EU leaders are furious with Trump's moves on Iran, and Brussels appeared set to welcome Pompeo only grudgingly, if at all.
Pompeo's plane arrived at its destination on Monday without formal confirmation from European leaders that any would actually meet him. Pompeo was coming to Brussels to discuss pressing matters, including Iran, with European officials, State Department spokesman Morgan Ortagus said.
"Secretary Pompeo will continue to coordinate closely with our allies and partners and ensure the security of our mutual interests in the Middle East and around the world," she said.
In Brussels, leaders sounded less than excited to see him.
"We were told during the night that he was planning to change his travel plans," EU foreign affairs chief, Federica Mogherini, told reporters ahead of a previously-scheduled meeting of top diplomats from the 28 European Union nations. "We will be here all day, with a busy agenda, so we will see during the day how and if we manage to arrange a meeting. He's always welcome, obviously, but there are no precise plans for the moment."
Mogherini planned to meet Monday afternoon with the foreign ministers of Germany, Britain and France, who are the European guarantors of the Iran deal.
The United States has bolstered its firepower in the Middle East in the last week, warning of imminent and direct threats from Iran to U.S. troops in Iraq and elsewhere. EU foreign ministers had planned to focus on other topics at Monday's meeting, talking about Iran only on the sidelines. But with both Iran and the United States quickly ramping up bellicose rhetoric, diplomats said they were increasingly concerned about an open conflict.
"We are very worried about the risk of a conflict happening by accident, with an escalation that is unintended really on either side," British Foreign Secretary Jeremy Hunt said ahead of the meeting. "Most of all, we need to make sure we don't end up putting Iran back on the path to renuclearization. Because if Iran becomes a nuclear power, its neighbors are likely to want to become nuclear powers. This is already the most unstable region in the world and this would be a massive step in the wrong direction."
European leaders agree with the United States that Iran's developing ballistic missile program and its belligerent behavior in its region and are problematic. But they differ about whether that means that the separate nuclear deal - a key part of President Barack Obama's foreign policy legacy - should be scrapped.
"This agreement is an important milestone in nuclear non-proliferation," French Foreign Minister Jean-Yves Le Drian told France's Le Parisien newspaper in an interview published Saturday. "It's a shame that the United States doesn't respect its commitments. Iran must show the political maturity to respect its own."
Pompeo had been previously scheduled to stop in Moscow on Monday before continuing on to Sochi. The State Department said Pompeo would meet with U.S. embassy staff and U.S. business leaders in the Russian capital and lay a wreath at the Tomb of the Unknown Soldier at the Kremlin wall.
But the Moscow portion of the visit was canceled in favor of the stop in Brussels, the State Department official told reporters shortly before Pompeo took off from Joint Base Andrews in Maryland.
Pompeo is still expected to travel on Tuesday to Sochi, the resort city where Putin often stays. A wide range of issues will be on the agenda in Sochi, Russian officials said, including policy in Venezuela, Iran, and Ukraine.
Pompeo's stop in Brussels is his second last-minute schedule change on a European visit this month. On May 7, Pompeo canceled a meeting with German Chancellor Angela Merkel in Berlin on a few hours' notice in order to travel to Iraq amid rising tensions with Iran.