Le tracce più antiche di insediamento umano nel distretto di Kostheim risalgono al Neolitico. In epoca romana, Kostheim aveva un'importanza strategica: inizialmente come base militare per assicurare il passaggio sul Meno, poi come testa di ponte per un ponte fisso in legno, costruito negli anni 75-110 d.C., che attraversava il fiume a ovest dell'attuale chiesa. Una strada militare da Kastel a Heddernheim toccava anche il villaggio; la cosiddetta Steinern Straße ne faceva parte. Molti reperti indicano che a Kostheim deve essersi gradualmente sviluppato un insediamento romano. Quest'epoca terminò nel 406 in una battaglia con gli Alani, i Suebi e i Vandali. Da allora Kostheim ha rivestito una grande importanza come punto di passaggio del fiume e si può ipotizzare che il sito di insediamento romano sia stato conquistato dalle tribù germaniche. Ciò è indicato anche dal nome del luogo, che può essere interpretato come un primo francone.

La notizia successiva di Kostheim è la sua prima menzione documentata nel 790, quando Carlo Magno emise due documenti nella "villa Copsistaino" il 31 agosto di quell'anno. Questo nome deriva dal latino "caput stagni", "testa sulla palude". Altre forme del nome sono "Chuffingstang", poi "Cufstain" e dal 1217 "C(h)ostheim". Il patronato sulla chiesa locale di San Kilian e le decime appartenevano al monastero di Altmünster di Magonza, che era il più importante proprietario di Kostheim. Ciò includeva la nomina e lo stipendio del sacerdote locale e del campanaro; il convento era anche responsabile della manutenzione dell'edificio della chiesa. Il monastero di Altmünster possedeva anche il traghetto sul Meno, che aveva affittato ai traghettatori di Kostheim nel 1432; aveva inoltre affittato le sue terre a Kostheim ad altre istituzioni ecclesiastiche. I signori di Eppstein avevano probabilmente anche un proprio maniero a Kostheim. Tuttavia, è difficile separare questo dal baliato su Kostheim, che avevano ricevuto in feudo già nel XII secolo e che esercitavano tramite sub-baliffi autorizzati. L'autorità ecclesiastica centrale era l'arcidiaconato del prevosto di San Pietro a Magonza, decanato di Kastel.

La giurisdizione sul sangue di Kostheim era esercitata dal tribunale distrettuale di Mechtildshausen, che apparteneva al distretto di Kostheim; il sindaco e gli assessori erano responsabili della giurisdizione civile e dell'amministrazione del villaggio. Come documentato fin dal 1330 circa, il tribunale si riuniva nel cortile dei Signori di San Stefan o davanti a esso, nel cortile del monastero di Altmünster o presso il muro di cinta della chiesa o davanti al cimitero. Un sindaco, Heinrich, viene citato per la prima volta nel 1281. Il numero degli assessori variava da tre a 13 e si è conservato un sigillo del tribunale del 1475. Per un certo periodo, il tribunale di Kostheim agì come alta corte per Kelkheim, Münster, Heidesheim, Budenheim e Hattersheim (1517).

Il distretto di Kostheim si estendeva a Ginsheim sulla riva sinistra del Meno e a Hochheim, Delkenheim, Erbenheim e Kastel sulla riva destra. Fino al 1528, Kostheim era uno dei luoghi in cui il governo locale e quello giudiziario erano divisi: Santo Stefano a Magonza deteneva il governo locale, mentre i Signori di Eppstein, in qualità di balivi, detenevano il governo giudiziario. Quando nel 1492 vendettero Kostheim ai langravi d'Assia, tra gli altri, mantennero il baliato fino alla vendita all'arcivescovo di Magonza nell'agosto del 1528. Nello stesso anno, i compiti del capo e del sottocapo, del maggiordomo, dell'agrimensore ecc. furono regolati in un Weistum. Vengono inoltre descritti dettagliatamente i compiti del parroco di San Kilian e del suo campanaro, che era sia organista che maestro di scuola. La scuola viene menzionata per la prima volta intorno al 1500. Kostheim rimase cattolica sotto la sovranità di Magonza, anche se la Riforma avrebbe trovato i suoi sostenitori nel villaggio. Kostheim fu bruciata nel 1552.

Kostheim visse tempi duri anche durante la Guerra dei Trent'anni. Il villaggio fu occupato dagli svedesi, che fondarono Gustavsburg sulla riva sinistra del Meno, nel distretto appartenente a Kostheim, come bastione pesantemente fortificato. I campi sulla riva sinistra del Meno e sulla Maaraue furono persi definitivamente da Kostheim, gli abitanti dovettero fare lavori forzati e soffrire sotto il peso dell'acquartieramento. Kostheim continuò a soffrire delle conseguenze della guerra per molto tempo; nel 1673, il villaggio aveva 113 proprietà, alcune delle quali erano "desolate e vuote". In totale furono contati 162 proprietari.

Già nel Medioevo Kostheim era circondata da una cinta muraria, con una porta superiore sulla Bruchstraße e una inferiore sul Meno. La disposizione delle strade di Mathildenstraße, Margarethenstraße e Herrenstraße (dove vivevano i Signori di San Stefan) ricorda ancora gli edifici medievali. I Letzmeister, eletti annualmente, erano responsabili della sicurezza delle porte e delle mura.

Nel XV secolo, Kostheim era un villaggio ricco, come si evince da un Salbuch in cui sono registrati i diritti feudali. Un fienile all'angolo tra Herrenstrasse e Burgstrasse è un residuo della fattoria delle decime. L'agricoltura e la viticoltura fiorirono nel XVIII secolo. Nel 1758, la scuola è stata elogiata in modo particolare nelle statistiche scolastiche. A capo dell'amministrazione nel XVIII secolo c'erano il balivo e il sottobalivo.

Questi tempi pacifici e prosperi terminarono con le guerre napoleoniche. Quando la Francia rivoluzionaria occupò Magonza nel 1792 e i francesi si affrontarono a Kastel e i tedeschi a Hochheim, Kostheim divenne un campo di battaglia. Dopo essere stata colpita più volte, era un campo di macerie e anche la chiesa parrocchiale fu distrutta. Nel 1803 Kostheim, come Kastel, entrò a far parte del distretto di Nassau-Usingen, e nel 1806 tornò a Magonza e divenne francese. Il confine tra Kostheim e Hochheim divenne il confine nazionale. Dopo il Congresso di Vienna, Kostheim e Kastel entrarono a far parte del Granducato d'Assia (Provincia di Rheinhessen, Cantone di Magonza). Nel 1835 Kostheim divenne una città e nel 1852 un distretto di Magonza. Nel 1806 la città contava 1.024 abitanti.

Nel 1808, su richiesta del sacerdote Rößler, Napoleone concesse a Kostheim 25 anni di esenzione fiscale - un favore che spinse il sacerdote Henrich a leggere un requiem per il defunto imperatore francese nel 1821, contrariamente al divieto sovrano ed ecclesiastico. Nel 1809, dopo un grave incendio, fu costruita la cosiddetta Neudörfche. Il villaggio fu ricostruito; nel 1830 il "villaggio" di Kostheim contava nuovamente 202 case con 1.272 abitanti e nel 1836 fu consacrata la nuova chiesa Kilianskirche.

La struttura economica originaria di Kostheim era caratterizzata dall'agricoltura, dalla frutticoltura e dalla viticoltura, ma uno skipper di Kostheim è menzionato già nel 1281 e nel 1662 il pescatore Lorenz Rhein apparteneva alla corporazione dei pescatori di Magonza. Grazie alla sua posizione favorevole alla confluenza del Meno e del Reno e ai collegamenti via ponte e via traghetto con la sponda meridionale del Meno che esistono da sempre, Kostheim è sempre stata un punto di trasbordo per merci di ogni tipo. A partire dal XVI secolo, il rafting è diventato una delle principali occupazioni degli abitanti di Kostheim. Nel 1894, un trattato di stato stabilì la regolamentazione del Basso Meno e l'espansione del porto per zattere di Kostheim. Originariamente a Kostheim c'erano cinque segherie, tre delle quali avevano diritti di zattera. L'industria di lavorazione del legname di Kostheim impiegava circa 200 persone fino a dopo la Seconda Guerra Mondiale. Oggi esiste ancora solo l'azienda Peter Eider.

Negli anni '60 del XIX secolo, la MAN si stabilì a Gustavsburg e si sviluppò fino a diventare una delle aziende leader nella costruzione di ponti in Germania. La fabbrica di cellulosa, aperta il 1° giugno 1885, divenne il più importante datore di lavoro. La fabbrica di fiammiferi di Kostheim (popolarmente nota come "Streichhölzer") fu costruita nel 1887 e impiegava circa 100 persone, per lo più donne. La produzione cessò alla fine del 1930. Nel 1926, Lindes Eismaschinen AG fondò una filiale a Kostheim con 250 dipendenti. Nel 1967, AEG acquisì il 75% delle azioni dello stabilimento Linde di Kostheim. Nel 1971 un grave incendio distrusse il magazzino e gli impianti di produzione. Dopo la ricostruzione nel 1989, la produzione è proseguita con il nome di Duofrost. Nel 2005, gli impianti sono stati venduti a Carrier GmbH e trasferiti nella Repubblica Ceca.

La necessaria modernizzazione dell'infrastruttura iniziò con l'apertura della ferrovia Taunusbahn sulla linea Wiesbaden-Francoforte nel 1840, e Kostheim perse il terreno necessario per la costruzione della ferrovia senza avere una propria stazione ferroviaria. Nel 1887/89 fu costruito un ponte fisso sul Meno. Nel 1907 Kostheim fu collegata alla rete tranviaria di Magonza.

In parte a causa del boom economico, alla fine del XIX secolo la popolazione aumentò da 2.971 abitanti nel 1875 a 4.832 nel 1895. Kostheim si espanse verso ovest attraverso Winterstraße intorno al 1900 e fino a Am Mainzer Weg nel 1916. Molti nomi di strade ricordano questo periodo: Wilhelmstraße, Viktoriastraße, Louisenstraße, Ludwigstraße. La comunità ricevette una scuola femminile nel 1875 e la scuola maschile fu ampliata nel 1897. Furono fondati numerosi club. Negli anni '70 del XIX secolo, furono costruiti nuovi edifici dall'altra parte della Winterstraße e della Berberichstraße. Da allora Kostheim ha avuto una congregazione protestante, che ha ottenuto una propria chiesa nel 1906. Gli abitanti ebrei, documentati a Kostheim dal 1820 circa, non formarono una propria comunità ma si orientarono verso Kastel. Il 1° gennaio 1913, Kostheim divenne parte della città di Magonza. Tuttavia, il distretto di Gustavsburg fu scorporato nel 1927. Dopo la Prima guerra mondiale, che portò a Kostheim lo stazionamento delle truppe di occupazione, fu creato il quartiere "Siedlung Kostheim", una città giardino con piccole case a schiera per 250 famiglie. Kostheim si sviluppò come un villaggio senza un centro distintivo e senza una chiara separazione tra fabbriche e aree residenziali.

Aziende industriali come MAN, Cellulose e Linde erano già orientate alle esigenze militari della guerra prima del 1936. La MAN produceva parti di ponti e scafi di navi, la Cellulose materiali di base per la produzione di munizioni, uniformi, carburante per l'aviazione e forniture mediche. La Seconda Guerra Mondiale ha causato danni significativi agli edifici della tenuta e di Alt Kostheim. La strada lungo Hochheimer Strasse fu quasi completamente distrutta. Le chiese cattoliche e l'attuale centro parrocchiale della tenuta furono colpiti dalle bombe. 113 persone rimasero uccise nei raid aerei. Dopo la Seconda Guerra Mondiale, furono costruiti nuovi quartieri residenziali, come il "Sampel", e nuove industrie.

Il 25 luglio 1945, Kostheim fu incorporata a Wiesbaden. Nel 2003, c'erano ancora sette piccole aziende agricole con una superficie inferiore ai due ettari. Inoltre, c'erano 13 aziende agricole a tempo pieno (per lo più in viticoltura, 66 ettari), che coltivavano un totale di 191 ettari di terreno. Oggi (al 1° gennaio 2016), a Kostheim vivono 14.076 persone in 6.752 famiglie.

Una caratteristica particolare è il pellegrinaggio annuale della parrocchia di San Kilian a Fischbach nel Taunus. Secondo dichiarazioni non documentate, il pellegrinaggio avrebbe portato all'immagine miracolosa nella cappella di Gimbach già nel 1444. Il motivo fu probabilmente una grande carestia. Altre fonti parlano del periodo intorno al 1666, un anno di grande peste in cui Kostheim fu risparmiata dall'epidemia. Nel 1828, il pellegrinaggio fu spostato nella chiesa parrocchiale di Fischbach su insistenza del governo del Ducato di Nassau. I cattolici della parrocchia vi si recano ancora oggi in pellegrinaggio penitenziale annuale.

Nel 1751, su una pietra di confine del 1603, sono stati ritrovati due coltelli da vite incrociati. L'immagine della pietra di confine, sotto forma di tenaglie d'argento su sfondo rosso, fu scelta come stemma di Kostheim.