Theophanous was born in Paphos, Cyprus on 24 March 1946. He migrated to Australia at the age of eight, with his mother, brother Theo Theophanous and sister; his father had arrived three years earlier. He grew up in Broadmeadows in Melbourne, entered Monash University and graduated with a Bachelor of Arts with First Class Honours. He gained a B.Litt. from Oxford University and a Ph.D. in Philosophy from Melbourne University. In 1980, his first book Australian Democracy in Crisis: a radical approach to Australian politics was published by Oxford University Press. He became a Lecturer in Politics, Melbourne State College and later in Social Theory at Melbourne University. He also lectured at the University of Nevada, USA, and as Senior Teaching Fellow at Monash University.
Dr Theophanous was first elected as the Labor member for the Melbourne electorate of Burke in 1980. He switched to the new safe Labor electorate of Calwell in 1984. Theophanous was heavily interested in immigration matters, and from 1989 to 1993, was Chairman of the Joint Standing Committee on Migration. In this capacity, Theophanous' committee produced a number of reports on immigration policy.
In 1993, Theophanous was appointed Parliamentary Secretary to the Minister for Housing, Local Government and Community Services and Parliamentary Secretary to the Minister for Health. In December, he was appointed Parliamentary Secretary to the Minister for Housing, Local Government and Human Services. In March 1994, he was appointed Parliamentary Secretary to Prime Minister Paul Keating, who had enjoyed his support in two caucus leadership ballots, which made him unusual in the Left grouping, who mostly supported Bob Hawke.
Theophanous also wrote two more books: "Understanding Social Justice: an Australian perspective" (1994) ; and "Understanding Multiculturalism and Australian Identity" (1995). Both books were officially launched by Prime Minister Keating and were used in a number of academic courses.
During 1998 Theophanous came under suspicion for being involved in migration fraud, and in July 1998 the National Crime Authority launched an investigation, codenamed Operation Legume. He was charged with defrauding the Commonwealth by making false representations in relation to an immigration matter, taking an unlawful inducement and soliciting an unlawful inducement.
Theophanous resigned from the Labor Party on 18 April 2000. His brother, Theo, condemned the resignation, calling it "an action taken by him with which I strongly disagree. I do not believe his actions are an appropriate response". At this time, Andrew Theophanous announced that he would serve out his term as an independent. During this period as an independent, he initiated a number of parliamentary motions on immigration, refugees, multicultural affairs and human rights. He recontested the seat as an independent candidate at the 2001 election. He polled 9.6% of the vote, with the support of the Unity Party, but the seat was won by the new Labor candidate and former staffer, Maria Vamvakinou.
Theophanous was jailed in 2002, having been sentenced to six years in prison, but only served two years and his barrister, Stephen Shirrefs S.C., instructed by Solicitors Doogue & O'Brien, successfully appealed one of the charges on which he had been convicted (that of conspiracy to defraud).
Theophanous is married to Dr. Kathryn Eriksson, an archaeologist. In November 2005, she was elected as a Brimbank Horseshoe Bend Ward Councillor. Theophanous' brother Theo Theophanous is a former state Labor politician.