Kabiru Ibrahim Gaya was elected to the Senate for Kano South in 2007. He was appointed to committees on Gas, Local and Foreign Debts, States & Local Government, and Upstream Petroleum Resources and Works. In a mid-term assessment of the performance of Senators, ThisDay newspaper noted that he sponsored the Finance Management and Accountability Bill, 2009, and the Millennium Development Agency Bill, 2009. He co-sponsored five motions and contributed well to debates in plenary. In May 2008, as chairman of the Senate committee on works, Kabiru Gaya lamented that some projects were going very slowly, but said the Senate would never subscribe to the idea of privatising Nigerian roads.
In November 2009 he supported a motion by the Kano chapter of the ANPP to allow the state governor, Ibrahim Shekarau, to nominate the ANPP candidate for the 2011 governorship elections. The presumptive nominee was Sheikh Ibrahim Khaleel. Kabiru Gaya ran for election as Senator for Kano South on the ANPP platform in April 2011, and was reelected.
Gaya was the Senate's Deputy Minority Whip from 2007 until 2011.