"If it's true that people with dark skin are being stopped for ID checks, that's totally unacceptable," Ullenhag told the TT news agency.
"ID checks based on a foreign appearance actually violate the rules that are currently in place."
Ullenhag's comments on Friday come following extensive media coverage detailing reports of police officers demanding that "foreign looking" commuters in the Stockholm metro system produce identification documents.
Police have defended their actions, explaining they only stop people who are suspected of committing a crime – such as trying to enter the metro without paying – and that the measures are tied to a wider effort to track down and deport immigrants who remain in the country illegally.
But Ullenhag was sceptical of officers' explanation, demanding instead that police "get to the bottom" of the situation.
"It's very troubling if people with dark skin colour or foreign appearances believe they may be stopped and subjected to an ID check," the minister said.
"This isn't the sort of situation we should have in the Stockholm metro system.
"People shouldn't be stopped by police on the basis of their appearance or skin colour."
Ullenhag explained further that Sweden strives to have an asylum policy marked by "solidarity and compassion" and anyone granted a residence permit should be allowed to stay in Sweden.
"But if someone isn't granted residency, that person doesn't have the right to stay," he said.
He argued there were "other methods" available to police for carrying out deportation orders that aren't based on the colour of a person's skin.
Peter Nilsson of the Stockholm border police also said it was wrong of officers to employ a strategy that involved targeting people who hadn't paid their public transit fares, but admitted that border police, which are always uniformed, do patrol the metro system.
However, he bristled at Ullenhag's comments, saying the minister should have "more concrete" evidence.
"There is too much in the media that is totally made up," said Nilsson.
According to Sören Clerton, head of the central border control unit with Sweden's National Bureau of Investigation (Rikskriminalpolisen, NBI), police must have "a well-founded reason", such as intelligence information, before performing internal border controls.
"We've understood that within the group of people who travel without paying a fare there are also people who don't have a permit to be here," he told TT.
Maria Ferm, migration policy spokeswoman for the Green Party, called the police's methods "discriminatory" and rejected claims by police that stories of people being forced to produce IDs because of their skin colour had been fabricated.
She plans to introduce a bill in parliament that would prohibit allowing police to perform checks on "foreign looking" people at the metro turnstiles.