He had previously served as both deputy prime minister (from 2001-2002)and defence minister (from 2002-2003), before succeeding Gennady Gagulia as Prime Minister on April 22, 2003. He had also served as head of the Abkhaz security service from 1999-2001.

As President Vladislav Ardzinba is seriously ill and has not appeared in public for more than two years, Khajimba has acted as a de facto head of state in his absence. In this role, he has met a number of political leaders, such as Igor Ivanov, foreign minister of Russia.

He has been tipped to succeed Ardzinba when the presidential term ends in October 2004.