In this study, we present a polarization-multiplexed, erbium-doped dual-comb fiber laser based on an all-polarization-maintaining cavity configuration. We observed that the dual-comb fiber laser easily realized the self-starting mode-locking operation due to the non-linear amplifying loop mirror (NALM) with a non-reciprocal phase shifter. Furthermore, owing to the sharing of the NALM part, the two outputs from this laser configuration had similar center wavelengths, with small different repetition rates ( increment f (rep)). In the free-running operation, the standard deviation of relative stability for & UDelta;f (rep) of 2.09 kHz was measured to be 1.59 Hz, and the full width at half-maximum of the relative beat note between the two frequency combs in the optical frequency domain was approximately 1 kHz. These results show that the two frequency combs from this laser configuration have high relative stability and mutual coherence.