ANKARA (Agencies) - President Barack Obama declared Monday during his first visit to a Muslim nation since his election that the United States was not, and never will be, at war with Islam. The United States is not and never will be at war with Islam, Obama said, in a major address to the Turkish parliament on the final leg of his tour of Europe, and said a major US Muslim outreach programme would be unveiled within months. President Obama said the United States and Turkey share a common threat from terrorism. He said while the US and Iraq are targeted by al-Qaeda terrorists, Turkey has been dealing with the PKK, the Kurdistan Workers Party. The PKK fights for self-rule in part of Turkey, launching attacks from hideouts in Iraq. Obama promised US support against those attacks. He said both the US and Turkey have an interest in making sure al-Qaeda doesnt have a safe haven in Pakistan or Afghanistan. He thanked Turkey for offering to help train and support Afghan troops. In talks with Turkish President Abdullah Gul and Prime Minister Recep Tayyip Erdogan, Obama hoped to sell his strategy for Afghanistan and Pakistan. He hoped to find welcoming ears given the new US focus on melding troop increases with civilian efforts to better the lives of people in both countries. Obama recognized past tensions in the US-Turkey relationship, but said things were on the right track now because both countries share common interests and are diverse nations. We dont consider ourselves Christian, Jewish, Muslim. We consider ourselves a nation bound by a set of ideals and values, Obama said of the United States. Turkey has similar principals. Obama also warned that Iran had to make a choice between having a nuclear weapon and building a better future for its people. I have made it clear to the people and leaders of the Islamic Republic that the United States seeks engagement based upon mutual interests and mutual respect, Obama said in address to the Turkish parliament Now, Irans leaders must choose whether they will try to build a weapon or build a better future for their people. The US President said that both the Annapolis agreement and the stalled roadmap laid out the route to Israeli-Palestinian peace. Obamas remarks came after Israels new Foreign Minister Avigdor Lieberman said last week that the 2007 Annapolis document did not bind Israel though he did accept the roadmap as the basis for progress. Let me be clear: the United States strongly supports the goal of two states, Israel and Palestine, living side by side in peace and security, Obama said. That is a goal shared by Palestinians, Israelis, and people of goodwill around the world. That is a goal that the parties agreed to in the roadmap and at Annapolis. And that is a goal that I will actively pursue as president. US President voiced robust backing for Turkeys bid to join the European Union, saying Ankaras inclusion in the block would strengthen Europe. Let me be clear: the United States strongly supports Turkeys bid to become a member of the European Union, Obama said during an address to the Turkish parliament. Turkey is bound to Europe by more than bridges over the Bosphorous... Europe gains by diversity of ethnicity, tradition and faith - it is not diminished by it. And Turkish membership would broaden and strengthen Europes foundation once more, he added.