Two biodegradation models are developed to represent natural attenuation of fuel-hydrocarbon contaminants as observed in a comprehensive natural-gradient tracer test in a heterogeneous aquifer on the Columbus Air Force Base in Mississippi, USA. The first, a first-order mass loss model, describes the irreversible losses of BTEX and its individual components, i.e., benzene (B), toluene (T), ethyl benzene (E), and xylene (X). The second, a reactive pathway model, describes sequential degradation pathways for BTEX utilizing multiple electron acceptors, including oxygen, nitrate, iron and sulfate, and via methanogenesis. The heterogeneous aquifer is represented by multiple hydraulic conductivity (K) zones delineated on the basis of numerous flowmeter K measurements. A direct propagation artificial neural network (DPN) is used as an inverse modeling tool to estimate the biodegradation rate constants associated with each of the K zones. In both the mass loss model and the reactive pathway model, the biodegradation rate constants show an increasing trend with the hydraulic conductivity. The finding of correlation between biodegradation kinetics and hydraulic conductivity distributions is of general interest and relevance to characterization and modeling of natural attenuation of hydrocarbons in other petroleum-product contaminated sites.