Syn amerykańskiegoczarnoskóregożołnierza stacjonującego w jednostce wojskowej w okolicach miasta Münster w Westfalii i Niemki, wdowy po zabitym na wojnie, brat 6 starszych sióstr. W roku 1967 dołączył do 3-ligowej drużyny z tego miasta - Preußen Münster. Następnie grał w pierwszoligowej drużynie MSV Duisburg, z którą zajął 7. miejsce na zakończenie rozgrywek. W tym sezonie zdobył w 19 meczach 5 bramek i 5 asyst. W 1968 roku trafił do belgijskiegoStandardu Liège, z którym to klubem zdobył 3 mistrzostwa Belgii (1968, 69, 70) Był także królem strzelców ligi belgijskiej w sezonie 1970/1971. Później odszedł do Ligue 1, gdzie grał w barwach Stade Laval, król strzelców Ligue 1 sezonu 1979/1980. Po tych osiągnięciach przeszedł do Kickers Offenbach, w którym występował do 1975 roku. W tym czasie zdobył w 93 meczach 52 bramki i zwrócił na siebie uwagę innych zespołów Bundesligi. Kupiła go Hertha BSC, w której w 26 meczach zdobył 14 bramek. Rok później grał już jednak w Borussii Dortmund, która awansowała do Bundesligi. W drużynie z rodzinnej Westfalii zagrał w 48 meczach i zdobył 18 bramek, ustępując umiejętnościami zdobywania bramek tylko łącznikowi Manfredowi Burgsmüllerowi. Po sezonie 1977/78 trafił do 2 ligi, gdzie w barwach FC Union Solingen z powodu częstych kontuzji zagrał tylko w dwóch spotkaniach. W wieku 34 lat trafił do 2 ligowego zespołu z Bremy – Werderu. W klubie znad Morza Północnego zdobył 29 bramek w 42 spotkaniach i walnie przyczynił się do awansu do Bundesligi.
Erwin w 1 lidze zagrał jeszcze w 33 spotkaniach i zdobył 9 bramek, jednak wobec konkurencji ze strony Norberta Meiera i Uwe Reindersa, a także 36 lat na karku odszedł do 2 ligowego VfL Osnabrück. To był ostatni rok jego kariery, zdobył w 28 spotkaniach 12 bramek. Ogółem w 2 Bundeslidze zagrał w 72 meczach i zdobył 41 bramek, zaś na pierwszoligowych boiskach zagrał w 219 spotkaniach, strzelając 98 bramek.
Kariera reprezentacyjna
W reprezentacji Niemiec Erwin Kostedde rozegrał 3 spotkania w 1974 i 1975 roku. Był pierwszym czarnoskórym reprezentantem tego kraju. Debiut zaliczył w spotkaniu z Maltą (22 grudnia 1974 roku), wygranym 1–0 przez zespół zachodnioniemiecki.
Problemy karne
Po zakończeniu kariery piłkarskiej Kostedde stracił swój majątek w wyniku nieudanych inwestycji. W 1990 roku oskarżono go o napad na salon gier w Coesfeld, jednak po kilku miesiącach został oczyszczony z zarzutów.
Jego bramka została uznana bramką miesiąca i bramką roku 1974, w zabawie stacji telewizyjnej ARD. Był to gol strzelony 18 października 1974 w spotkaniu Kickers Offenbach z Borussią Mönchengladbach (Kostedde strzelił na 3-3 z woleja). do audycji radiowej.
