The purpose of this study is to investigate the influence of fiscal decentralization on the efficiency of social security in China since the realization of social security was promoted and some relevant policies were implemented in 21 century. This study uses China’s provincial-level data of 31 regions from 2000 to 2009 and uses two inputs and three outputs to calculate the efficiency scores as the dependent variables. The inputs are the proportions of expenditures for social security and employment effort to total public expenditures and the proportions of hygiene, social security, and social welfare employed people to total employed people. The outputs are the coverage rate of urban basic pension insurance, the coverage rate of unemployment insurance, and the coverage rate of urban basic medical care insurance. Then, this study establishes four specifications of the Tobit model. Other factors, gross regional product per capita (PGRP), the degree of openness (OPEN), the scale of provincial government (SOG), the quadratic term of the former (SOGSQ), area dummy variables, and time dummy variables, are added into the Tobit model. The primary finding of this study is that fiscal decentralization has a positively non-monotonic influence on the efficiency of social security. This contributes positively to the efficiency of provincial government’s social security, but this positive influence does not always exist.