Billing fraud by health care providers is a widespread problem to a country’s health care system. This article develops a general theory for estimating the billing error in medical claims within pre-specified error bound using auxiliary information on the average payment amount made by all persons in the population. Estimation methods with pre-specified sample size cannot be used to achieve the fixed-width confidence interval for billing error. In this article we propose two two-stage procedures for accuracy in estimating billing error in medical claims using sample standard deviation and sample Gini’s mean difference as estimators of population standard deviation. This problem is the same as constructing a fixed-width confidence interval for billing error. In two-stage estimation procedures, the final sample size is not fixed in advance by using supposed unknown population parameter(s). Data in two-stage procedures are collected in two stages in which the final sample size is based on the estimate of the unknown parameter(s) in the first stage. The comparison of the proposed two-stage procedures are examined using a Monte Carlo simulation study. © 2020 South African Statistical Association