In one embodiment, a network flow sampling system includes packet processing circuitry to process data packets of multiple network flows, and an adaptive policer to, for each one network flow of the multiple network flows compute a quantity of flow-specific sampling credits to be assigned to the one network flow responsively to a quantity of the network flows currently being processed by the packet processing circuitry, assign the flow-specific sampling credits to the one network flow, sample at least one of the data packets of the one network flow responsively to availability of the flow-specific sampling credits of the one network flow yielding sampled data, while applying sampling fairness among the network flows, and remove at least one of the flow-specific sampling credits of the one network flow from availability responsively to sampling the at least one data packet of the one network flow.