Pracował początkowo z drużynami juniorskimi i uczelnianymi, w 1970 objął po raz pierwszy funkcję trenera drużyny ligi zawodowej NBA Phoenix Suns; w 1972 przeszedł do Atlanta Hawks, następnie odpowiadał za dobór kadr w ekipie mistrza NBA, Golden State Warriors. Kolejnymi klubami w karierze trenerskiej Fitzsimmonsa były Buffalo Braves (1977-1978) i Kansas City Kings; praca z tym zespołem przyniosła mu nagrodę Trenera Roku NBA w 1979. W 1981 został wpisany do sportowej Hall of Fame stanu Missouri.
W 1988 powrócił do pracy z ekipą Phoenix Suns. Doprowadził zespół do finału Konferencji Zachodniej NBA (porażka z Los Angeles Lakers) w 1989, ponownie zdobywając tytuł Trenera Roku. W kolejnym sezonie zespół pod kierownictwem Fitzsimmonsa wziął rewanż na ekipie z Los Angeles w półfinale Konferencji Zachodniej, w finale jednak nie sprostał tym razem Portland Trailblazers. W 1991 Phoenix Suns odpadło już w pierwszej rundzie fazy play-off ligi NBA, ulegając Utah Jazz; w 1992 ekipa dotarła do półfinału Konferencji Zachodniej, gdzie przegrała ponownie z Portland Trailblazers. Po tej porażce Fitzsimmons, który w ciągu sezonu osiągnął (jako 6. trener w historii NBA) zwycięstwo nr 800 w karierze, zrezygnował z dalszej pracy i został wiceprezydentem klubu.
Ponownie pracował jako trener Phoenix Suns w latach 1996-1997; doprowadził po raz kolejny zespół do fazy play-off, ale po nieudanym starcie w kolejnym sezonie (przegrane osiem pierwszych spotkań) zakończył karierę trenerską. Łącznie zaliczył jako trener 832 zwycięstw i 775 porażek.
