We present a streamline-based approach for estimating relative permeabilities from production data. The streamline approach offers two principal advantages. First, we can analytically compute the sensitivity of the production response with respect to relative permeability parameters. The approach is extremely fast and requires a single streamline simulation run. Second, we can exploit the analogy between streamlines and seismic ray tracing to develop a formalism for efficient inversion of production data. For relative permeability representations we have used the commonly used power functions and also a more flexible representation through the use of B-splines. The relative advantages of these representations are examined through inversions of water-cut data from a nine-spot pattern. Finally, we address the underlying challenges associated with the simultaneous estimation of absolute and relative permeabilities from production data. We systematically investigate the nonuniqueness associated with the inverse problem and quantitatively evaluate the role of additional data such as pressure response in addition to water-cut history at the wells.