A dual-wavelength passively mode-locked Yb-doped fiber laser (YDFL) based on the interaction of graphene and fiber-taper evanescent field is reported. Using optical evanescent-light deposition technique, graphene-polymer nanocomposites in aqueous suspension are coated onto taper waist region. The graphene-based tapered-fiber as a saturable absorber has the advantages of flexibility, all-fiber configuration, and high optical damage threshold. Based on the saturable absorption of this graphene-based component and the cavity-birefringent filtering characteristics, the stable dual-wavelength mode-locked operation is obtained, by properly adjusting the polarization state of the laser cavity. The two mode-locked wavelengths of YDFL are 1034.77 nm and 1038.85 nm, and the mode-locked repetition rate is 1.09 MHz at the second harmonic frequency, and the intracavity pulse energy can reach 35 nJ.