The efficiency and effectiveness of local governments has become one of the main points of interest in public sector administration, as decision and policy making gradually move from the central to the local level. This paper introduces an efficiency analysis framework based on accrual accounting data obtained from the local governments’ financial statements. Data envelopment analysis is used to obtain efficiency estimates, which are analyzed through a second stage regression against a set of efficiency explanatory factors. Furthermore, the optimal reallocation of the municipalities’ inputs and outputs is explored to provide policy recommendations that a central government could implement in a budget reduction context. Detailed empirical results are presented from a panel data set of Greek municipalities over the period 2002–2009.