About 10,000 citizens, religious leaders and politicians, among them Chancellor Angela Merkel, joined the event, which started with a wreath-laying ceremony at the French embassy and an imam reciting Koranic verses condemning the taking of life.
Gauck used his speech to send a message of reassurance to Germany's four-million-strong Muslim community, a day after a record 25,000 people joined a protest march by a populist anti-Islamic movement.
"We are all Germany," he said.
"We, democrats with our different political, cultural and religious backgrounds; we, who respect and need each other; we, who want to live life… in unity, justice and freedom," Gauck said in his speech at Berlin's Brandenburg Gate.
"The vast majority of Muslims feel they belong to our open society… Germany has become more diverse through immigration – religiously, culturally and mentally."
"Our answer to the fundamentalism of the Islamist perpetrators of violence is democracy, respect for the law, respect for each other, respect for human dignity. This is our way of life!"
People at the rally applauded his message of inter-faith unity that came a day after the 12th rally by Germany's new right-wing movement the "Patriotic Europeans Against the Islamisation of the West", or PEGIDA, which has spawned smaller clone groups across Germany and as far as Norway.
Merkel – who this week stressed that "Islam is part of Germany" – said earlier Tuesday that "hatred, racism and extremism have no place in this country… We are a country based on democracy, tolerance and openness to the world."
'Terror: not in our name'
Tuesday's vigil and rally was organised by the Central Council of Muslims under the banner "Let's be there for each other. Terror: not in our name!"
"Today we all want to express our solidarity with the French people," its chairman Aiman Mazyek said in his opening address. "The terrorists did not win and terrorists won't win in future.
"Today we say, along with the French people and many people around the world: 'Je suis Charlie'," he added, employing the international message of solidarity with the artists killed at the Charlie Hebdo magazine.
The vice president of the Central Council of Jews in Germany, Abraham Lehrer, said in his speech that in the French attacks, cartoonists were murdered because they stood up for free expression, police because they sought to protect them, and Jews simply "because they were Jews".
Lehrer said it would be wrong "to suspect all Muslims or even to disparage their religion. We completely condemn reprisals such as attacks on mosques."
But he said it was up to Muslims to counter the fear and terror spread by "radicalised, fanatical Islam" in Asia, Africa and the Middle East.
After speeches by Christian, Jewish and Muslim religious leaders, all observed a minute's silence.
The Muslim community rally came after 100,000 people took to the streets across Germany Monday in counter-demonstrations against PEGIDA, and to voice support for multiculturalism.
Merkel, who is often known to avoid controversial issues, has weighed in strongly, condemning PEGIDA's leaders for having "hatred in the hearts".
Her comments were broadly hailed in the media, but not everyone agreed.
"Naturally, Muslims belong in our society," said Merkel's former interior minister Hans-Peter Friedrich, a Bavarian conservative.
"But the question is knowing what constitutes the identity of a country, and in Germany it is a Christian identity built on Judeo-Christian roots."
Bild, Germany's top-selling daily, said the Paris attacks seemed to have shaken the usually unflappable Merkel, a pastor's daughter who grew up in the communist East.
"She has two issues where, when she speaks, she doesn't sound like she is simply droning on with platitudes: religion and freedom," it said, noting the rare public signs of emotion she showed with Hollande at Sunday's solidarity march.
"She knows that gestures are now necessary… it is about freedom and protection from a terrorist war."