Waterflooding is a common secondary oil recovery process. Performance of waterfloods in mature fields with a significant number of wells can be improved with minimal infrastructure investment by optimizing injection/production rates of individual wells. However, a major bottleneck in the optimization framework is the large number of reservoir flow simulations often required. In this work we propose a new method based on streamline-derived information that significantly reduces these computational costs in addition to making use of the computational efficiency of streamline simulation itself. We seek to maximize the longterm net present value of a waterflood by determining optimal individual well rates, given an expected albeit uncertain oil price and a total fluid injection volume. We approach the optimization problem by decomposing it into two stages which can be implemented in a computationally efficient manner. The twostage streamline-based optimization approach can be an effective technique when applied to reservoirs with a large number of wells in need of an efficient waterflooding strategy over a 5 to 15 year period.