Rudi Gutendorf stammt aus Koblenz - einem Ort, an den es ihn immer wieder zurückzog und in dessen Nähe er heute wieder lebt. Nationalspieler Jupp Gauchel holte ihn 1942 als junges Stürmertalent in die erste Mannschaft der damals hochklassigen TuS Neuendorf, kurz bevor Rudi Gutendorf zum Kriegsdienst beordert wurde und in Gefangenschaft geriet. Nach dem Weltkrieg setzte er seine Karriere bei TuS Neuendorf fort und gelangte mit der Elf bis ins Halbfinale der Deutschen Meisterschaft.
Nach seinem Trainerstart in der Schweiz war 1961 Tunesien Gutendorfs erste internationale Station. Später folgten Einsätze in über 30 Ländern der Welt, u.a. als Nationaltrainer von Chile, Bolivien, Australien, Tansania, Ghana, Fidschis und China. Sein Blick ging dabei immer wieder über den Spielfeldrand hinaus - er interessierte sich für die Lebensverhältnisse in diesen Ländern, lernte Salvador Allende kennen, erklärte dem König von Tonga den "Rudi-Riegel" und besuchte Klaus Kinski bei dessen Dreharbeiten im Amazonas-Urwald.
In der deutschen Bundesliga führte Gutendorf den MSV Duisburg zur Vizemeisterschaft, den FC Schalke 04 ins Halbfinale des Europapokals, trainierte u.a. den HSV, TSV 1860 München, VfB Stuttgart, Tennis Borussia Berlin, Hertha BSC und Fortuna Köln.
In Ruanda, seiner vorläufig letzten Station, gelang es ihm, aus den verfeindeten Volksgruppen eine gemeinsame Mannschaft zu formen.