Although institutional autonomy has recently received significant attention from scholars and policy-makers in much of the world, few studies have been made of the universities in transition towards institutional autonomy in post-Soviet countries. Autonomy and its related concept of public accountability are relatively new phenomena in Kazakhstan's higher education system. Learning to be autonomous presents challenges for the universities in transition from state central control to the decentralization of education system. Based on qualitative data analysis, this paper examines university leaders and faculty members' understandings, experiences and perspectives in relation to the transition to autonomy at their institutions. Our findings show that the challenges of the transition to institutional autonomy combine Soviet legacies, current difficulties of central control, entrenched practices of university leadership and legally limited practices of the faculty. We argue that for actual autonomy to take place, the discussed socially and ideologically constructed complexities of the universities in transition need to be dealt with by policy-makers and researchers and, more importantly, university leadership.