The young woman, whose name was not disclosed, was stopped on the first day of his trial this week at the security controls at Oslo's courthouse, police officer Jan Kvarme told commercial television TV2.
She was held in detention for 24 hours before being taken to the airport on Tuesday and deported to Germany, Kvarme said.
"As she went through the controls, it became clear she wanted to get in and see Breivik," he said." After checking with authorities abroad, we received confirmation that this woman had been convicted of disturbing the peace on several occasions in her country."
"We therefore decided that she was not welcome in our country," he added, confirming that she was of German nationality but refusing to disclose her name.
"It has been said that she claimed to be (Breivik's) girlfriend, but we can't speculate on that. We have no information to indicate that she really is his girlfriend," he said.
The woman, interviewed by TV2 as she queued up outside the courthouse, said she had promised Breivik she would attend his trial for two weeks.
Asked if she and the 33-year-old rightwing extremist had written letters to each other, she replied by nodding her head. She told TV2 she had arrived in Oslo on Sunday, the day before the start of the trial, and was from Stuttgart.
Breivik is now allowed to receive letters in his cell at the high-security Ila prison outside Oslo, after a court-ordered ban lasting several months was lifted.
According to an anti-racist activist who has monitored the entrances to the courthouse since Monday, several Norwegian far-right extremists have been seen entering the building to sit in on the proceedings, in the seats reserved for the general public, TV2 said.
Breivik has been charged with "acts of terror" for murdering 77 people last year.
On July 22, he first killed eight people last July when he set off a bomb in a van parked outside buildings housing the offices of Labour Prime Minister Jens Stoltenberg, who was not present at the time.
He then travelled to Utoya island where, dressed as a police officer, he spent more than an hour methodically shooting at hundreds of people attending a Labour Party youth summer camp.
The shooting spree claimed 69 lives, mostly teens trapped on the small island surrounded by icy waters. It was the deadliest massacre ever committed by a lone gunman.
Breivik entered a plea of not guilty at the start of his trial, saying his acts were "cruel but necessary."