With the provincial audit institutions in China from 2002 to 2013 as the research data, this paper uses Data Envelopment Analysis based on BCC Model with Variable Returns to Scale to measure the performance value of the provincial audit institutions, and then it studies the influence that the tenure in office of the leaders, the governors and the heads-the directors of audit institutions has exerted on the audit performance. The result shows that tenure in office of the governors has a U-shaped nonlinear relationship with the audit performance, and tenure in office of the directors of audit institutions is positively correlated with the audit performance, and the staggered tenure in office between the governor and the director of audit will improve the audit performance. This conclusion will enrich the references of provincial audit institutions performance. Besides, it can provide reference for the Party Central Committee, the Leading Party Group of State Audit Commission, Provincial Party Committee and the Provincial Government in appointing and dismissing the governors and the directors of audit institutions effectively.