Motivated by possible generalizations to more complex multiphase multicomponent systems in higher dimensions, we develop an Eulerian-Lagrangian numerical approximation for a system of two conservation laws in one space dimension modeling a simplified two-phase flow problem in a porous medium. The method is based on following tracelines, so it is stable independent of any CFL constraint. The main difficulty is that it is not possible to follow individual tracelines independently. We approximate tracing along the tracelines by using local mass conservation principles and self-consistency. The two-phase flow problem is governed by a system of equations representing mass conservation of each phase, so there are two local mass conservation principles. Our numerical method respects both of these conservation principles over the computational mesh (i.e., locally), and so is a fully conservative traceline method. We present numerical results that demonstrate the ability of the method to handle problems with shocks and rarefactions, and to do so with very coarse spatial grids and time steps larger than the CFL limit. © 2012 Society for Industrial and Applied Mathematics.