We report observations of phase-locking phenomena between two Josephson soliton (fluxon) oscillators biased in self-resonant modes. The locking strength was measured as a function of bias conditions. A frequency tunability of the phase-locked oscillators up to 7% at 10 GHz was observed. Two coupled perturbed sine-Gordon equations were derived from an equivalent circuit consisting of inductively coupled, nonlinear, lossy transmission lines. These equations were solved numerically to find the locking regions. Good qualitative agreement was found between the experimental results and the calculations based on the model.