Availability of inorganic nutrients, particularly nitrogen and phosphorous, is often a primary control on crude oil hydrocarbon degradation in marine systems. Many studies have empirically determined optimum levels of inorganic N and P for stimulation of hydrocarbon degradation. Nevertheless, there is a paucity of information on fundamental kinetic parameters for nutrient enhanced crude oil biodegradation that can be used to model the fate of crude oil in bioremediation programmes that use inorganic nutrient addition to stimulate oil biodegradation. Here we report fundamental kinetic parameters (Ks and qmax) for nitrate-and phosphate-stimulated crude oil biodegradation under nutrient limited conditions and with respect to crude oil, under conditions where N and P are not limiting. In the marine sediments studied, crude oil degradation was limited by both N and P availability. In sediments treated with 12.5 mg/g of oil but with no addition of N and P, hydrocarbon degradation rates, assessed on the basis of CO2 production, were 1.10 ± 0.03 μmol CO2/g wet sediment/day which were comparable to rates of CO2 production in sediments to which no oil was added (1.05 ± 0.27 μmol CO2/g wet sediment/day). When inorganic nitrogen was added alone maximum rates of CO2 production measured were 4.25 ± 0.91 μmol CO2/g wet sediment/day. However, when the same levels of inorganic nitrogen were added in the presence of 0.5% P w/w of oil (1.6 μmol P/g wet sediment) maximum rates of measured CO2 production increased more than four-fold to 18.40 ± 1.04 μmol CO2/g wet sediment/day. Ks and qmax estimates for inorganic N (in the form of sodium nitrate) when P was not limiting were 1.99 ± 0.86 μmol/g wet sediment and 16.16 ± 1.28 μmol CO2/g wet sediment/day respectively. The corresponding values for P were 63 ± 95 nmol/g wet sediment and 12.05 ± 1.31 μmol CO2/g wet sediment/day. The qmax values with respect to N and P were not significantly different (P < 0.05). When N and P were not limiting Ks and qmax for crude oil were 4.52 ± 1.51 mg oil/g wet sediment and 16.89 ± 1.25 μmol CO2/g wet sediment/day. At concentrations of inorganic N above 45 μmol/g wet sediment inhibition of CO2 production from hydrocarbon degradation was evident. Analysis of bacterial 16S rRNA genes indicated that Alcanivorax spp. were selected in these marine sediments with increasing inorganic nutrient concentration, whereas Cycloclasticus spp. were more prevalent at lower inorganic nutrient concentrations. These data suggest that simple empirical estimates of the proportion of nutrients added relative to crude oil concentrations may not be sufficient to guarantee successful crude oil bioremediation in oxic beach sediments. The data we present also help define the maximum rates and hence timescales required for bioremediation of beach sediments.