The concept of efficiency in the public services is more complex than the concept of efficiency in the private, profit-oriented sector. Consequently, the measurement of efficiency in the public services is very complex and implies more effort in the identification of relevant outputs and inputs. One of the segments of the public service system in the Republic of Croatia is the Customs Administration, which is an important regulator of Croatian international trade and freight traffic, and also a significant tax authority. This research is focused on determining the relative efficiency of regional organizational units of the Customs administration on the basis of its most relevant inputs and outputs. Conclusions were made by the processing of data obtained directly from the Customs Administration by using the method of data envelopment analysis. The results obtained, in the end, indicate the need to establish new and different territorial organizational structure for the Customs Administration.