Connolly was elected to the PEI Legislature in 1982 and served as Opposition Critic for Health & Social Services and the Status of Women. He served on the Legislative Committee on Quality of Life and Co-Chaired a Liberal Party Task Force on Job Creation & Community Development. When the Joe Ghiz Government was sworn into office in May 1986 he was appointed Chairman of Policy Board, responsible for ensuring that all government programs and initiatives tied into the overall policy thrust of government. Re-elected in 1989, he was appointed Minister of Education, as well as Minister Responsible for Status of Women & Minister Responsible for Native Affairs. In September 1992, he was elected Vice-Chairman of the Council of Ministers of Education, Canada. In March 1993, Connolly was re-elected as MLA for the Charlottetown Riding of 6th Queens and appointed to a Cabinet Committee for Public Consultation, later serving as Minister of Higher Education in the Catherine Callbeck Government. He was also appointed a commissioner for the PEI Electoral Reform Commission, mandated under the Public Enquiries Act to review and recommend changes to PEI's electoral boundaries. In 1996 Connolly was re-elected to a fifth consecutive term as the MLA for the newly created single member district of Charlottetown-Rochford Square. In March 1999 he was appointed Leader of the Official Opposition, serving in that position until he left politics in 2000. He was appointed to The National Parole Board in 2002, serving for seven years.
