An asymmetric graphene-coated elliptical dielectric nano-parallel wires’ waveguide is proposed. By using the multipole method, in the two elliptic cylindrical coordinate systems, firstly, the longitudinal component of the electric field and the magnetic field are expressed by Mathieu functions, then the corresponding angular and radial components are obtained by Maxwell’s equations. The graphene is regarded as a zero-thickness interface with surface conductivity, and the boundary conditions are applied to these interfaces by the point-matching method. A linear algebraic equation system is obtained finally. The effective refractive indices and the field distributions of modes can be obtained by numerically solving the equation. The six lowest order modes supported by the proposed structure are classified, and the dependence of the characteristics of these modes, separately, on the working wavelength, the graphene Fermi energy and waveguide structure parameters are studied. The real part of the effective refractive index, the propagating length, and the quality factor are used to judge the performance of the waveguide. The results reveal that the characteristics of these modes can be greatly changed by altering the working wavelength of the waveguide, the Fermi energy of graphene, and the spacing between nanowires. When the length of the semi-major and the semi-minor axes of the nanowires are modified, the real part of the effective refractive index, the propagating length, and the quality factor can only be changed finely. At the same time, the results obtained by the multipole method are completely consistent with the results from the finite element method. By comparing the performances among the fundamental mode supported by the single graphene-coated elliptical dielectric nanowire, the symmetric graphene-coated elliptical dielectric nano-parallel wires, and the asymmetric graphene-coated elliptical dielectric nano-parallel wires by the means of the FEM based on commercial software (COMSOL), we find that the performances of the proposed waveguide in this paper are superior to those of the other two waveguides. This work can provide a theoretical basis for the design, fabrication, and application of asymmetric graphene-coated elliptical dielectric nano-parallel wires’ waveguide. The proposed structure is expected to be used in the mode conversion and coupling in the future devices.