Mosul, Iraq's second largest city, was taken by ISIS in a Blitzkrieg-like sweep in June.
Todenhoefer managed to visit the mosque there where the leader of ISIS, Abu Bakr al-Bagdadi, gave his only public address.
And he saw the realities of daily life under ISIS, with all shops having to close for prayers in the middle of the day.
"There is an awful sense of normalcy in Mosul," Todenhoefer said in an exclusive interview with CNN.
"130,000 Christians have been evicted from the city, the Shia have fled, many people have been murdered and yet the city is functioning and people actually like the stability that the Islamic State has brought them."
Nonetheless, he says, there is an air of fear among residents: "Of course many of the them are quite scared, because the punishment for breaking the Islamic State's strict rules is very severe."
According to ISIS's leadership, the group's fighters managed to take Mosul with only about 300 men, even though more than 20,000 Iraqi army soldiers were stationed there when the attack was launched.
Todenhoefer spoke with several ISIS fighters who took part in the operation.
"It took us about four days to take Mosul," a young fighter told him.
"So you were only about 300 men and you defeated 20,000 troops in four days?" Todenhoefer asked.
"Well, we didn't attack them all at once, we hit their front lines hard, also using suicide attacks. Then the others fled very quickly," the fighter explained. "We fight for Allah, they fight for money and other things that they do not really believe in."
Glow in their eyes
Todenhoefer told CNN the enthusiasm the ISIS militants showed was one thing that stood out.
"When we stayed at their recruitment house, there were 50 new fighters who came every day," Todenhoefer said. "And I just could not believe the glow in their eyes. They felt like they were coming to a promised land, like they were fighting for the right thing.
"These are not stupid people. One of the people we met had just finished his law degree, he had great job offers, but he turned them down to go and fight ... We met fighters from Europe and the United States. One of them was from New Jersey. Can you imagine a man from New Jersey traveling to fight for the Islamic State?"
He went on to say that one of ISIS's main points of strength is their fighters' willingness -- even their will -- to die on the battlefield.
Todenhoefer met one somewhat overweight recruit in a "safe house" who said he wears a suicide belt to every battle because he is too chubby to run away if he is cornered and would choose to blow himself up, rather than be captured.
ISIS also has a track record of abusing, torturing and executing prisoners of war. Todenhoefer was briefly able to speak to a Kurdish captive while in Mosul. The captive claimed he had not been tortured, but Todenhoefer said he found that hard to believe.
"This was a broken man," Todenhoefer said. "It was very sad to see a person in this state. He was just very weak and very afraid of his captors."
Todenhoefer conducted the interview with the prisoner while several ISIS fighters stood guard. He asked the man whether he knew what would happen to him.
"I do not know," the captive told him. "My family does not even know I am still alive. I hope that maybe there will be some sort of prisoner exchange."
Child ISIS fighters
Todenhoefer was also taken to see child soldiers outfitted with Islamic State gear and brandishing AK-47s. One of the boys seemed very young but claimed he had already gone to battle for ISIS.
"How old are you?" Todenhoefer asked.
"I am 13 years old," the boy replied -- though he looked even younger than that.
One of the most remarkable episodes of Todenhoefer's trip to the ISIS-controlled region came when he was able to conduct an interview with a German fighter who spoke on behalf of ISIS's leadership.
The man -- clearly unapologetic about the group's transgressions -- vowed there was more to come; he also issued a warning to Europe and the United States.
"So you also want to come to Europe?" Todenhoefer asked him.
"No, we will conquer Europe one day," the man said. "It is not a question of if we will conquer Europe, just a matter of when that will happen. But it is certain ... For us, there is no such thing as borders. There are only front lines.
"Our expansion will be perpetual ... And the Europeans need to know that when we come, it will not be in a nice way. It will be with our weapons. And those who do not convert to Islam or pay the Islamic tax will be killed."
Todenhoefer asked the fighter about their treatment of other religions, especially Shia Muslims.
"What about the 150 million Shia, what if they refuse to convert?" Todenhoefer asked.
"150 million, 200 million or 500 million, it does not matter to us," the fighter answered. "We will kill them all."
The interview became testy when they reached the topic of beheadings and enslavement, especially of female captives.
"So do you seriously think that beheadings and enslavement actually signal progress for humanity?" Todenhoefer asked.
"Slavery absolutely signals progress," the man said. "Only ignorant people believe that there is no slavery among the Christians and the Jews. Of course there are woman who are forced into prostitution under the worst circumstances.
"I would say that slavery is a great help to us and we will continue to have slavery and beheadings, it is part of our religion ... many slaves have converted to Islam and have then been freed."
The ISIS spokesman blamed the beheading of captured Western journalists and aid workers on the policies of the United States.
"People should really think about the case of James Foley," he said. "He did not get killed because we started the battle. He got killed because of the ignorance of his government that did not give him any help."
Even with recent gains by Kurdish forces against ISIS in northern Iraq, Todenhoefer sees the extremist group as entrenched, building state institutions, and that it shows no sign of losing its grip in the main areas it controls in Iraq and Syria.
"I think the Islamic State is a lot more dangerous than Western leaders realize," he said. "They believe in what they are fighting for and are preparing the largest religious cleansing campaign the world has ever seen."
READ MORE: Fighting for Kobani -- from a distance