Kariera reprezentacyjna Fleminga również wiąże się ściśle z osobą Johna McEnroe. W latach 1979–1984 Fleming wystąpił piętnastokrotnie w reprezentacji USA w Pucharze Davisa, wyłącznie jako deblista, zawsze mając za partnera McEnroe. Pozostawali przez lata niepokonani, dopiero w ostatnim meczu – finale Pucharu Davisa 1984 – serię Amerykanów przerwali Szwedzi Edberg i Järryd (trofeum w tymże roku zdobyli Szwedzi). Dzięki tym występom Fleming miał znaczący udział w trzykrotnych triumfach zespołu amerykańskiego. W 1979 zdobył punkt w jednej z wcześniejszych rund, później pozycję reprezentacyjnych deblistów przejęli Bob Lutz i Stan Smith (McEnroe grał natomiast także w rundach finałowych w grze pojedynczej); zarówno w 1981, jak i w następnym roku, Fleming z McEnroe zdobywali już punkty w finałach, kolejno przeciwko Argentyńczykom i Francuzom. W 1984 i 1985 Fleming był ponadto w składzie zespołu, który sięgnął po Drużynowy Puchar Świata.

W parze McEnroe–Fleming za lidera uchodził McEnroe, młodszy o cztery lata od partnera. Fleming, podobnie jak jego partner, zdołał osiągnąć pozycję lidera w światowym rankingu gry podwójnej – po raz pierwszy w czerwcu 1984.