The administrative costs of providing health insurance in the US are very high, but their determinants are poorly understood. We advance the nascent literature in this field by developing new measures of billing complexity for physician care across insurers and over time, and by estimating them using a large sample of detailed insurance “remittance data” for the period 2013–15. We found dramatic variation across different types of insurance. Fee-for-service Medicaid is the most challenging type of insurer to bill, with a claim denial rate that is 17.8 percentage points higher than that for fee-for-service Medicare. The denial rate for Medicaid managed care was 6 percentage points higher than that for fee-for-service Medicare, while the rate for private insurance appeared similar to that of Medicare Advantage. Based on conservative assumptions, we estimated that the health care sector deals with $11 billion in challenged revenue annually, but this number could be as high as $54 billion. These costs have significant implications for analyses of health insurance reforms.