He first ran for the legislature in 1998, making an unsuccessful bid for the New York State Senate in the 30th district, losing the Democratic primary to Eric Schneiderman. When Assemblyman Edward C. Sullivan announced his retirement in 2002, O'Donnell was one of eight Democrats who entered the race to succeed him. In the crowded primary election held on September 10, 2002, O'Donnell won 34 percent of the vote, twice as much as his nearest competitor. In the general election that followed, he prevailed with 82 percent of the vote. O'Donnell was the first openly gay man elected to the New York State Assembly and currently serves as one of six LGBT members of the New York Legislature, alongside Assemblymembers Deborah Glick, Micah Kellner, Matthew Titone and Harry Bronson, as well as Senator Brad Hoylman. His campaigns have frequently won the backing of the Gay & Lesbian Victory Fund. He ran uncontested in the 2008 and 2010 general elections. He was opposed in the September 13, 2016 Democratic Primary by Steven M. Appel, but won over 73% of the vote.
Committees
As of 2017, O'Donnell serves as Chair of the Assembly Committee on Tourism, Parks, Arts and Sports Development and Chair of the Subcommittee on Criminal Procedure. Previously, O'Donnell served as Chair of the Assembly Committee Corrections, Assembly Committee on Ethics and Guidance, as well as Chair of the Subcommittee on Criminal Procedure of the Assembly Judiciary Committee. He also serves on a number of full committees, namely:
Committee on Codes
Committee on Education
Committee on Environmental Conservation
Committee on Puerto Rican/Hispanic Task Force
Legislation
On June 19, 2007 O'Donnell ushered the Marriage Equality Act, a bill that would have legalized gay marriage in New York State, to passage by a vote of 85–61. Although the bill passed the Assembly and had the support of then-Governor Eliot Spitzer, the Republican-controlled State Senate did not take up the measure. O'Donnell once again led the fight for a same-sex marriage bill in 2009, shepherding it to passage twice more, by a vote of 89–52 in May, and by a vote of 88–51 in December. O'Donnell introduced the Marriage Equality bill in the Assembly for the 2011-2012 legislative session on May 10, 2011. The Marriage Equality Act was passed by the NYS Assembly on June 15, 2011, and passed the NYS Senate and was signed into law by Governor Andrew Cuomo slightly before midnight on Friday, June 24, 2011. O'Donnell was also the prime sponsor of the Dignity for All Students Act, New York's anti-bullying law. The law was signed into law by Governor Paterson on September 8, 2010, and was one of the first laws in New York history to explicitly include protections based on gender identity and expression. O'Donnell was an outspoken opponent of the legalization of mixed martial arts in New York State, at one point likening the grappling of the two combatants to "gay porn, only with a different ending."
Public Advocate race
In 2019, he sought the New York City Public Advocate seat being vacated by Letitia James, who had been elected for New York State Attorney General. In what The Villager described as "one of the most jam-packed elections in recent memory," he lost to Jumaane Williams at 2.9 percent to the latter's 33 percent.