As member of the Ontario Liberal Party he ran for the Legislative Assembly of Ontario in the riding of Waterloo North in the 1990 provincial election. He finished a poor third against Progressive ConservativeElizabeth Witmer thus becoming the first Liberal to lose that riding in over 23 years. He won an easy victory to the House of Commons of Canada three years later and was subsequently re-elected four times, all by comfortable margins. Telegdi was appointed parliamentary secretary to the Minister of Citizenship of Immigration on July 16, 1998, but resigned the position on May 18, 2000, as he objected to certain provisions in the government's proposed Citizenship Act. He was concerned with a clause that gave Canada's parliament, rather than the courts, the right to remove a person's citizenship, and in particular Helmut Oberlander's who was a constituent of the riding he then represented. Commenting on this issue, he said "For me, my citizenship comes before my party." During this controversy, Telegdi argued that placing parliament above the courts on citizenship issues was similar to "what Hitler used to do". Telegdi was widely criticized for this comment and the Canadian Jewish Congress and called for Telegdi's removal from the Liberal caucus. In response, Telegdi noted that his stepfather was a Jewish refugee from Romania, and claimed his comments had been reported out of context in a sensational manner. He also issued the following statement: "What I have said is that a liberal democratic state such as Canada should never remove citizenship lightly. That is what Hitler did to Jews, Gypsies and many others. That is what Stalin did to millions. All totalitarian regimes have engaged in these practices."
He also issued an apology for his comments to the House of Commons. Telegdi also engaged in a public dispute with Liberal Party activist Warren Kinsella during this period. After Kinsella criticized Telegdi's comments on the Citizenship Act, Telegdi wrote a letter calling on Kinsella to resign as Jean Chrétien's spokesperson. Telegdi is a liberal on most social issues. He is a strong supporter of gay rights and same-sex marriage. He also opposed the 2003 invasion of Iraq, expressing concern that the American approach of "pre-emptive strikes" would create new problems and undermine multilateral institutions. For several years, Telegdi was a supporter of Paul Martin in his bid to succeed Jean Chrétien as leader of the Liberal Party. Soon after Martin succeeded Chrétien as Liberal leader and Prime Minister, Telegdi was appointed parliamentary secretary to the Prime Minister with special emphasis on Aboriginal Affairs. He held this position until just after the 2004 election and prior to the 2008 election was vice-chair of the Standing Committee on Citizenship and Immigration. He lost to Conservative candidate Peter Braid by an initial count of 48 votes in the 2008 federal election. A judicial recount was ordered, as the margin of victory was less than 0.1%. The final validated count, showing errors in two polls, confirmed his opponent had won the seat by 17 votes, the smallest margin of victory in the 2008 federal election. He campaigned again in the 2011 federal election and lost to Braid by 2,114 votes.
