The purpose of this paper is to propose a guide for graduate trace studies (GTS) to be adopted by universities and other higher education institutions (HEIs) in East Africa. Their essential role notwithstanding, graduate tracer studies present viable opportunities through which quality assurance (QA) can be institutionalized and mainstreamed in activities of HEIs in East Africa (EA). Moi University is embracing graduate tracer studies triggered by the DAAD UNITRACE initiative much for the reason of generating from immediate users of university academic services, nuanced and evidenced information requisite for improvement of university education and service programmes. This paper is presented as a proposal for a GTS guide for East Africa higher institutions of learning (HEIs) that if accepted shall benchmark through GTS methodology and results for use to entrench a culture of quality assurance at universities. The objective of this paper thus, is to propose a methodological guide for graduate trace studies suitable for East Africa Universities. Using experiences, methodologies, results and lessons of a pioneer graduate tracer survey conducted at Moi University, the paper posits a seven staged GTS guide that fits the needs for East Africa. Information feedback, recommendations and evaluative proposals made by graduates about their experiences during degree study and transition to the job market immensely help to improve the quality of education and services at the University (table 1). This paper should arouse our desire to initiate and entrench GTS as means by which we can achieve quality assurance at universities and HEIs in East Africa. Originality and value of this paper lies in its first ever proposal for a guide for GTS suitable and domesticated for East Africa.