Born in Aden, Basindawa served as Minister of Foreign Affairs from 1993 to 1994. He was a member of Yemen's ruling party, but resigned in the early 2000s to join the opposition to President Ali Abdullah Saleh as an independent.
In November 2011, following months of unrest, Basindawa was nominated by the Yemeni opposition to lead the first government after the ouster of President Saleh. On 27 November 2011, he was named Prime Minister by Vice President Abdrabbuh Mansur Hadi. He and the members of his cabinet were sworn in on 10 December 2011.
On 31 August 2013, Basindawa narrowly escaped an assassination attempt when gunmen opened fire on his convoy.