Najstarsze ślady osadnictwa ludzkiego w dzielnicy Kostheim pochodzą z okresu neolitu. W czasach rzymskich Kostheim miało znaczenie strategiczne: początkowo jako baza wojskowa do zabezpieczenia przeprawy przez Men, a następnie jako przyczółek stałego drewnianego mostu, który został zbudowany w latach 75-110 n.e. i przecinał rzekę na zachód od dzisiejszego kościoła. Przez wioskę przebiegała również droga wojskowa z Kastel do Heddernheim, której częścią była tak zwana Steinern Straße. Wiele znalezisk wskazuje, że rzymska osada musiała stopniowo rozwijać się w Kostheim. Epoka ta zakończyła się w 406 r. bitwą z Alanami, Suebi i Wandalami. Od tego czasu Kostheim miało duże znaczenie jako przeprawa przez rzekę i można przypuszczać, że rzymska osada została przejęta przez plemiona germańskie. Wskazuje na to również nazwa miejscowości, którą można interpretować jako wczesnofrankijską.

Kolejną wiadomością o Kostheim jest jego pierwsza udokumentowana wzmianka z 790 roku, kiedy to Karol Wielki wydał dwa dokumenty w "villa Copsistaino" 31 sierpnia tego samego roku. Nazwa ta pochodzi od łacińskiego "caput stagni", "głowa na bagnach". Inne formy tej nazwy to "Chuffingstang", następnie "Cufstain", a od 1217 r. "C(h)ostheim". Patronat nad miejscowym kościołem św. Kiliana oraz dziesięciny należały do klasztoru Altmünster z Moguncji, który był najważniejszym właścicielem ziemskim w Kostheim. Obejmowało to mianowanie i uposażenie miejscowego księdza i dzwonnika; klasztor był również odpowiedzialny za utrzymanie budynku kościoła. Klasztor Altmünster był również właścicielem promu przez Men, który w 1432 r. wydzierżawił kostheimskim przewoźnikom; wydzierżawił również swoją ziemię w Kostheim innym instytucjom kościelnym. Panowie z Eppstein prawdopodobnie posiadali również własny dwór w Kostheim. Trudno jednak oddzielić to od bailiwick nad Kostheim, które otrzymali jako lenno już w XII wieku i sprawowali przez upoważnionych sub-komorników. Centralną władzą kościelną był archidiakonat proboszcza św. Piotra w Moguncji, dekanat Kastel.

Jurysdykcję sądową nad Kostheim sprawował sąd okręgowy w Mechtildshausen, który należał do okręgu Kostheim; burmistrz i wójtowie byli odpowiedzialni za jurysdykcję cywilną i administrację wsi. Jak udokumentowano od około 1330 r., sąd spotykał się na dziedzińcu lub przed dziedzińcem panów św. Stefana, na dziedzińcu klasztoru Altmünster lub na murze kościelnym lub przed cmentarzem. Burmistrz, Heinrich, został wymieniony z imienia po raz pierwszy w 1281 roku. Liczba wójtów wahała się od trzech do 13, a z 1475 r. zachowała się pieczęć sądowa. Przez pewien czas sąd w Kostheim działał jako sąd wyższej instancji dla Kelkheim, Münster, Heidesheim, Budenheim i Hattersheim (1517).

Okręg Kostheim rozciągał się do Ginsheim na lewym brzegu Men oraz do Hochheim, Delkenheim, Erbenheim i Kastel na prawym brzegu. Do 1528 r. Kostheim było jednym z miejsc z podzieloną władzą lokalną i sądowniczą: St Stephen's w Moguncji sprawował władzę lokalną, podczas gdy panowie Eppstein, jako komornicy, sprawowali władzę sądowniczą. Kiedy sprzedali Kostheim między innymi landgrafom Hesji w 1492 roku, zachowali baliwat aż do sprzedaży arcybiskupowi Moguncji w sierpniu 1528 roku. W tym samym roku obowiązki głównego i podgłównego urzędnika, brodacza, mierniczego itp. zostały uregulowane w Weistum. Szczegółowo opisano również obowiązki proboszcza parafii św. Kiliana i jego dzwonnika, który był zarówno organistą, jak i dyrektorem szkoły. Pierwsza wzmianka o szkole pochodzi z około 1500 roku. Kostheim pozostało katolickie pod zwierzchnictwem Moguncji, mimo że reformacja znalazła swoich zwolenników w wiosce. Kostheim zostało spalone w 1552 roku.

Kostheim przeżyło również ciężkie czasy podczas wojny trzydziestoletniej. Wioska została zajęta przez Szwedów, którzy założyli Gustavsburg na lewym brzegu Men w dzielnicy należącej do Kostheim jako silnie ufortyfikowany bastion. Pola na lewym brzegu Menu i na Maaraue zostały utracone dla Kostheim na dobre, mieszkańcy musieli wykonywać prace przymusowe i cierpieć pod ciężarem ćwiartowania. Kostheim jeszcze przez długi czas odczuwało skutki wojny; w 1673 r. wieś liczyła 113 posesji, z których część była "opuszczona i pusta". Łącznie naliczono 162 właścicieli.

Kostheim było otoczone murami miejskimi już w średniowieczu, z górną bramą na Bruchstraße i dolną bramą na Main. Układ ulic Mathildenstraße, Margarethenstraße i Herrenstraße (gdzie mieszkali panowie św. Stefana) nadal przypomina średniowieczne budynki. Corocznie wybierani Letzmeisters byli odpowiedzialni za bezpieczeństwo bram i murów.

W XV wieku Kostheim było zamożną wioską, o czym świadczy Salbuch, w którym zapisano opłaty feudalne. Stodoła na rogu Herrenstrasse i Burgstrasse jest pozostałością po gospodarstwie dziesięcinnym. Rolnictwo i uprawa winorośli kwitły w XVIII wieku. W 1758 r. szkoła została wyróżniona w statystykach szkolnych. Na czele administracji w XVIII wieku stał główny komornik i pod-komornik.

Te spokojne i dostatnie czasy dobiegły końca wraz z wojnami napoleońskimi. Kiedy rewolucyjna Francja zajęła Moguncję w 1792 roku i Francuzi stanęli naprzeciw siebie w Kastel, a Niemcy w Hochheim, Kostheim stało się polem bitwy. Po kilkukrotnym ostrzale było to pole gruzów, a kościół parafialny również został zniszczony. W 1803 r. Kostheim, podobnie jak Kastel, stało się częścią dystryktu Nassau-Usingen, a w 1806 r. powróciło do Moguncji i stało się francuskie. Granica między Kostheim i Hochheim stała się granicą państwową. Po Kongresie Wiedeńskim Kostheim i Kastel zostały włączone do Wielkiego Księstwa Hesji (prowincja Rheinhessen, kanton Moguncja). W 1835 r. Kostheim stało się miastem, a w 1852 r. dzielnicą Moguncji. W 1806 r. miasto liczyło 1024 mieszkańców.

W 1808 r., na prośbę księdza Rößlera z Kostheim, Napoleon przyznał Kostheim 25 lat zwolnienia podatkowego - przysługa, która skłoniła księdza Henricha do odczytania requiem dla zmarłego cesarza Francuzów w 1821 r., wbrew suwerennemu i kościelnemu zakazowi. W 1809 r. po wielkim pożarze zbudowano tak zwany Neudörfche. Wieś została odbudowana; w 1830 r. "wieś" Kostheim ponownie liczyła 202 domy z 1272 mieszkańcami, a w 1836 r. konsekrowano nowy kościół Kilianskirche.

Pierwotna struktura gospodarcza Kostheim charakteryzowała się rolnictwem, sadownictwem i uprawą winorośli, ale już w 1281 r. wspomina się o szyprze z Kostheim, a w 1662 r. rybak Lorenz Rhein należał do cechu rybaków z Moguncji. Młyn istniał najpóźniej od 1293 r. Ze względu na korzystne położenie u zbiegu Men i Ren oraz połączenia mostowe i promowe z południowym brzegiem Men, które istniały od wczesnej historii, Kostheim zawsze było punktem przeładunkowym dla wszelkiego rodzaju towarów. Od XVI wieku rafting stał się jednym z głównych zajęć mieszkańców Kostheim. W 1894 r. traktat państwowy określił regulację Dolnego Menu i rozbudowę portu flisackiego w Kostheim. Pierwotnie w Kostheim znajdowało się pięć tartaków, z których trzy posiadały prawo do spławiania drewna. Przemysł drzewny w Kostheim zatrudniał około 200 osób aż do II wojny światowej. Dziś nadal istnieje tylko firma Peter Eider.

W latach sześćdziesiątych XIX wieku firma MAN osiedliła się w Gustavsburgu i stała się jedną z wiodących firm zajmujących się budową mostów w Niemczech. Fabryka celulozy, otwarta 1 czerwca 1885 roku, stała się najważniejszym pracodawcą. Fabryka zapałek w Kostheim (popularnie zwana "Streichhölzer") została zbudowana w 1887 roku i zatrudniała około 100 osób, głównie kobiet. Produkcję zakończono pod koniec 1930 roku. W 1926 r. firma Lindes Eismaschinen AG założyła oddział w Kostheim zatrudniający 250 pracowników. W 1967 r. firma AEG nabyła 75% udziałów w fabryce Linde w Kostheim. Poważny pożar w 1971 roku zniszczył magazyn i zakłady produkcyjne. Po odbudowie w 1989 roku produkcja była kontynuowana pod nazwą Duofrost. W 2005 roku zakłady zostały sprzedane firmie Carrier GmbH i przeniesione do Czech.

Niezbędna modernizacja infrastruktury rozpoczęła się wraz z otwarciem kolei Taunusbahn na linii Wiesbaden-Frankfurt w 1840 r., przy czym Kostheim straciło grunty potrzebne pod budowę kolei, nie posiadając własnej stacji kolejowej. W latach 1887/89 zbudowano stały most nad Menem. W 1907 r. Kostheim zostało podłączone do sieci tramwajowej Moguncji.

Częściowo w wyniku boomu gospodarczego, liczba ludności wzrosła pod koniec XIX wieku z 2,971 w 1875 r. do 4,832 w 1895 r. Kostheim rozszerzyło się na zachód przez Winterstraße około 1900 r. i aż do Am Mainzer Weg w 1916 r. Wiele nazw ulic nawiązuje do tego okresu. Wiele nazw ulic przypomina ten czas: Wilhelmstraße, Viktoriastraße, Louisenstraße, Ludwigstraße. W 1875 r. gmina otrzymała szkołę dla dziewcząt, a w 1897 r. rozbudowano szkołę dla chłopców. Założono liczne kluby. W latach siedemdziesiątych XIX wieku wzniesiono nowe budynki po drugiej stronie Winterstrasse i Berberichstrasse. Od tego czasu w Kostheim istniał zbór protestancki, który w 1906 r. otrzymał własny kościół. Żydowscy mieszkańcy, których obecność w Kostheim udokumentowano od około 1820 r., nie utworzyli własnej gminy, lecz skupili się wokół Kastel. 1 stycznia 1913 r. Kostheim stało się częścią Moguncji. Dzielnica Gustavsburg została jednak wydzielona w 1927 roku. Po I wojnie światowej, która przyniosła Kostheim stacjonowanie wojsk okupacyjnych, dzielnica "Siedlung Kostheim" została stworzona jako miasto-ogród z małymi domami szeregowymi dla 250 rodzin. Kostheim rozwinęło się w wioskę bez wyraźnego centrum i bez wyraźnego podziału na fabryki i obszary mieszkalne.

Przedsiębiorstwa przemysłowe, takie jak MAN, Cellulose i Linde, już przed 1936 r. były nastawione na wojskowe wymogi wojny. MAN produkował części mostów i kadłuby statków, Cellulose podstawowe materiały do produkcji amunicji, mundurów, paliwa lotniczego i środków medycznych. Druga wojna światowa pozostawiła znaczne zniszczenia w budynkach osiedla i Alt Kostheim. Ulica wzdłuż Hochheimer Strasse została prawie całkowicie zniszczona. Kościoły katolickie i obecne centrum parafialne na osiedlu zostały trafione bombami. W nalotach zginęło 113 osób. Po II wojnie światowej powstały nowe osiedla mieszkaniowe, takie jak "Sampel", oraz nowe zakłady przemysłowe.

25 lipca 1945 r. Kostheim zostało włączone do Wiesbaden. W 2003 r. nadal istniało siedem małych gospodarstw rolnych o powierzchni mniejszej niż dwa hektary. Ponadto istniało 13 gospodarstw pełnoetatowych (głównie w uprawie winorośli, 66 hektarów), które uprawiały łącznie 191 hektarów ziemi. Obecnie (stan na 1 stycznia 2016 r.) w Kostheim mieszka 14 076 osób w 6 752 gospodarstwach domowych.

Szczególną cechą jest coroczna pielgrzymka parafii św. Kiliana do Fischbach w Taunus. Według nieudokumentowanych przekazów, pielgrzymka ta miała doprowadzić do cudownego obrazu w kaplicy w Gimbach już w 1444 roku. Powodem był prawdopodobnie wielki głód. Inne źródła mówią o okresie około 1666 r., roku wielkiej zarazy, w którym Kostheim zostało oszczędzone przez epidemię. W 1828 r. pielgrzymka została przeniesiona do kościoła parafialnego w Fischbach pod naciskiem rządu Księstwa Nassau. Katolicy z parafii nadal odbywają tam coroczną pielgrzymkę pokutną.

W 1751 r. na kamieniu granicznym z 1603 r. znaleziono dwa skrzyżowane noże do winorośli. W formie srebrnych szczypiec na czerwonym tle, wizerunek na kamieniu granicznym został wybrany jako herb Kostheim.