When State Representative E. Denise Lee opted to run for a seat in the Florida Senate rather than seek re-election in 2002, Gibson ran to succeed her in the 15th District, which was based in downtown Jacksonville in Duval County. She faced Mack Freeman, a former television reporter, and Rahman Johnson, a Duval County Soil and Water Conservation District Commissioner, in the Democratic primary. Gibson campaigned on attracting high-paying jobs to the region, increasing workforce development, amending the state education funding formula to send more funds to area schools, and on her experience in "people issues," noting, "The function of a legislative leader isn't just thinking of what bills to bring about, it's about connecting to people to make things happen in the district." She ended up defeating her opponents by a comfortable margin of victory, winning 42% of the vote to Freeman's 30% and Johnson's 28%. She faced Adam Norwood, the Libertarian nominee, in the general election, whom she defeated in a landslide with 81% of the vote. Gibson was re-elected without opposition in 2004, and in 2006, was challenged in the Democratic primary by Fullwood, who had defeated her when she ran for the City Council in 1999. The Florida Times-Union endorsed Gibson for re-election, praising her as "a strong leader who deserves more time in office," noting, "Gibson has shown an ability to get things done without membership in the majority party." Ultimately, Gibson won renomination, scoring 57% of the vote to Fullwood's 43%, and advanced to the general election, where she was re-elected without opposition. She was re-elected unopposed once again in 2008, and could not seek another term in 2010 due to term limits.
Florida Senate
In 2011, when State SenatorTony Hill resigned from the legislature to serve as Jacksonville Mayor Alvin Brown's Director of Federal Policy, a special election was called to replace him in the 1st district, which stretched from Jacksonville to Daytona Beach, including parts of southern Duval County, western Flagler County, eastern Putnam County, St. Johns County, and northern Volusia County. Gibson had already filed to run for the Senate in 2012, when Hill would have been prevented from seeking another term due to term limits, so she filed to run in the special election to replace him. She faced former State Representative Terry L. Fields, Ramon Day, and Leandrew Mills in the Democratic primary, and during the campaign, a group supporting Gibson attacked Fields for having a property tax exemption "on a house he says he does not live in." During the campaign, Gibson was endorsed by the Florida Times-Union, which praised her for experience, energy, wisdom, and "ability to work across the aisle to build alliances," specifically noting her advocacy for transportation and economic development. Gibson ended up defeating her opponents by a wide margin, receiving 62% of the vote to Fields's 32%, Day's 3%, and Mills's 3%. She did not face an opponent in the general election and won unopposed. When the state's legislative districts were redrawn in 2012, Gibson was moved into the 9th district, which included only parts of Jacksonville in Duval County, dropping her previous district's arm down to Daytona Beach. She won her party's nomination unopposed and faced Cherron Newby, the Republican nominee, in the general election. Gibson earned the endorsement of the Florida Times-Union, which praised her as an active legislator who "has focused on developing, saving homes, transportation and education," and criticized her opponent as inexperienced and not qualified for office. Owing to the liberal lean of the district, Gibson defeated Newby with 64% of the vote to win her second term in the legislature. Gibson's district was redrawn again in 2016 after court-ordered redistricting, and she won re-election to a more compact 6th district in Jacksonville.
