Най-старите следи от човешко заселване в областта Костхайм датират от неолита. През римската епоха Костхайм е имал стратегическо значение: първоначално като военна база за осигуряване на прехода през Майн, а след това като плацдарм за неподвижен дървен мост, построен през 75-110 г. от н.е. и пресичащ реката западно от днешната църква. Военният път от Кастел до Хедернхайм също е засягал селото; така наречената Щайнерн Щрасе е била част от него. Много находки показват, че в Костхайм постепенно трябва да се е развило римско селище. Тази епоха приключва през 406 г. в битка с алани, суеби и вандали. От това време Костхайм е с голямо значение като речен преход и може да се предположи, че мястото на римското селище е било превзето от германските племена. За това свидетелства и името на местността, което може да се тълкува като раннофранкско.

Следващото известие за Костхайм е първото му документирано споменаване през 790 г., когато Карл Велики издава два документа във "вила Копсистайно" на 31 август същата година. Това име произлиза от латинското "caput stagni", "глава на блато". Други форми на името са "Chuffingstang", след това "Cufstain", а от 1217 г. "C(h)ostheim". Патронажът над местната църква "Свети Килиан", както и десятъкът, са принадлежали на майнцкия девически манастир Алтмюнстер, който е бил най-важният земевладелец в Костхайм. Това включвало назначаването и заплащането на местния свещеник и на камбанаря; манастирът отговарял и за поддръжката на църковната сграда. Манастирът в Алтмюнстер е притежавал и ферибота през Майн, който през 1432 г. е отдал под наем на костехаймските фериботници; манастирът е отдавал под наем земите си в Костхайм и на други църковни институции. Владетелите на Епщайн вероятно са имали и собствено имение в Костхайм. Трудно е обаче да се отдели то от съдебния контрол над Костхайм, който те са получили като легация още през XII в. и са упражнявали чрез упълномощени подконтролни. Централната църковна власт е била архидяконството на протойерей на Свети Петър в Майнц, Кастелски деканат.

Кръвната юрисдикция над Костхайм се упражнявала от окръжния съд в Мехтилдсхаузен, който принадлежал към окръг Костхайм; кметът и старейшините отговаряли за гражданската юрисдикция и администрацията на селото. Както е документирано от около 1330 г. насам, съдът е заседавал в двора на господарите на Свети Стефан или пред него, в двора на манастира Алтмюнстер, на стената на църквата или пред гробището. За първи път през 1281 г. се споменава името на кмета Хайнрих. Броят на старейшините варира между трима и 13, а от 1475 г. е запазен съдебен печат. За известно време съдът в Костхайм изпълнява функциите на върховен съд за Келкхайм, Мюнстер, Хайдсхайм, Буденхайм и Хатерсхайм (1517 г.).

Районът на Костхайм се простирал до Гинсхайм на левия бряг на Майн и до Хоххайм, Делкенхайм, Ербенхайм и Кастел на десния бряг. До 1528 г. Костхайм е едно от местата с разделена местна и съдебна власт: местната власт се упражнява от Сент Стефан в Майнц, а съдебната - от господарите на Епщайн в качеството им на съдебни изпълнители. Когато през 1492 г. те продават Костхайм на ландграфовете на Хесен, наред с другото, запазват и съдебното правораздаване, докато през август 1528 г. го продават на архиепископа на Майнц. През същата година задълженията на главния и подглавния писар, бейдъл, геодезист и т.н. са регламентирани в един вайстум. Подробно са описани и задълженията на енорийския свещеник на Свети Килиан и на неговия звънар, който е бил едновременно органист и учител. Училището се споменава за първи път около 1500 г. Костхайм остава католически под властта на Майнц, въпреки че Реформацията ще намери своите поддръжници в селото. Костхайм е опожарен през 1552 г.

Костхайм преживява тежки времена и по време на Тридесетгодишната война. Селото е окупирано от шведите, които основават Густавсбург на левия бряг на Майн в района, принадлежащ на Костхайм, като силно укрепен бастион. Полетата на левия бряг на Майн и на река Маарауе са загубени завинаги за Костхайм, жителите са принудени да работят принудително и страдат под тежестта на разквартируването. Костхайм дълго време продължава да страда от последиците на войната; през 1673 г. селото има 113 имота, някои от които са "запустели и празни". Бяха преброени общо 162 собственици.

Още през Средновековието Костхайм е бил обграден с градска стена, с горна порта на Брухщрасе и долна порта на Майн. Разположението на улиците Матилденщрасе, Маргаретенщрасе и Херенщрасе (където са живели господарите на Свети Стефан) все още напомня за средновековните сгради. Ежегодно избираните лецмайстори са отговаряли за сигурността на портите и стените.

През XV в. Костхайм е било богато село, както личи от един Salbuch, в който са записани феодалните налози. Хамбар на ъгъла на Херенщрасе и Бургщрасе е остатък от ферма за десятък. През XVIII в. земеделието и лозарството процъфтяват. През 1758 г. училището е отбелязано със специална похвала в училищната статистика. Начело на администрацията през XVIII в. стоят главният съдебен изпълнител и помощник-съдебният изпълнител.

Тези мирни и благоденстващи времена приключват с Наполеоновите войни. Когато през 1792 г. революционна Франция окупира Майнц и французите се изправят един срещу друг в Кастел, а германците - в Хоххайм, Костхайм се превръща в бойно поле. След като е обстрелван няколко пъти, той се превръща в поле от развалини, а енорийската църква също е разрушена. През 1803 г. Костхайм, както и Кастел, става част от областта Насау-Усинген, а през 1806 г. се връща към Майнц и става френски. Границата между Костхайм и Хоххайм става национална граница. След Виенския конгрес Костхайм и Кастел стават част от Великото херцогство Хесен (провинция Райнхесен, кантон Майнц). през 1835 г. Костхайм става град, а през 1852 г. - окръг на Майнц. През 1806 г. градът има 1024 жители.

През 1808 г., по молба на костхаймския свещеник Рьослер, Наполеон освобождава Костхайм от данъци за 25 години - услуга, която кара свещеник Хенрих да прочете реквием за починалия френски император през 1821 г., противно на владетелската и църковната забрана. През 1809 г. след голям пожар е построена така наречената Нойдорфче. Селото е възстановено; през 1830 г. "селото" Костхайм отново има 202 къщи с 1272 жители, а през 1836 г. е осветена новата църква Килианскирхе.

Първоначалната икономическа структура на Костхайм се характеризира със земеделие, овощарство и лозарство, но още през 1281 г. се споменава капитан на Костхайм, а през 1662 г. рибарят Лоренц Рейн е член на рибарската гилдия в Майнц. Мелница съществува най-късно от 1293 г. Благодарение на благоприятното си местоположение при сливането на Майн и Рейн и на мостовите и фериботните връзки с южния бряг на Майн, съществуващи от ранната история, Костхайм винаги е бил пункт за претоварване на всякакви стоки. От XVI в. нататък рафтингът се превръща в един от основните поминъци на жителите на Костхайм. През 1894 г. с държавен договор се урежда регулирането на Долен Майн и разширяването на пристанището за салове в Костхайм. Първоначално в Костхайм е имало пет дъскорезници, три от които са имали право на салове. В дървопреработвателната промишленост на Костхайм до края на Втората световна война работят около 200 души. Днес все още съществува само фирмата на Петер Ейдър.

През 60-те години на XIX в. компанията MAN се установява в Густавсбург и се превръща в една от водещите фирми за строителство на мостове в Германия. Фабриката за целулоза, открита на 1 юни 1885 г., се превръща в най-важния работодател. Фабриката за мачове в Костхайм (популярна като "Streichhölzer") е построена през 1887 г. и в нея работят около 100 души, предимно жени. Производството е преустановено в края на 1930 г. През 1926 г. Lindes Eismaschinen AG основава клон в Костхайм с 250 служители. През 1967 г. AEG придобива 75% от акциите на завода на Linde в Костхайм. Голям пожар през 1971 г. унищожава склада и производствените помещения. След възстановяването през 1989 г. производството продължава под името Duofrost. През 2005 г. заводите са продадени на Carrier GmbH и са преместени в Чешката република.

Необходимата модернизация на инфраструктурата започва с откриването на железопътната линия Taunusbahn по линията Висбаден-Франкфурт през 1840 г., като Костхайм губи земята, необходима за изграждането на железницата, без да има собствена железопътна гара. През 1887/89 г. е построен стационарен мост над Майн. През 1907 г. Костхайм е свързан с трамвайната мрежа на Майнц.

Отчасти в резултат на икономическия подем, в края на XIX в. населението се увеличава от 2971 души през 1875 г. на 4832 души през 1895 г. Около 1900 г. Костхайм се разширява на запад чрез Винтерщрасе, а през 1916 г. - до Ам Майнцер Вег. Много имена на улици напомнят за това време: Вилхелмщрасе, Викториящрасе, Луишенщрасе, Лудвигщрасе. През 1875 г. общината получава девическо училище, а през 1897 г. е разширено училището за момчета. Основани са многобройни клубове. През 70-те години на XIX в. са построени нови сгради от другата страна на Винтерщрасе и Берберихщрасе. От това време в Костхайм има протестантска община, която през 1906 г. получава собствена църква. Еврейските жители, които са документирани в Костхайм от около 1820 г., не образуват своя собствена общност, а се ориентират към Кастел. На 1 януари 1913 г. Костхайм става част от град Майнц. През 1927 г. обаче от него е отделен районът Густавсбург. След Първата световна война, която донася на Костхайм настаняването на окупационни войски, кварталът "Siedlung Kostheim" е създаден като град-градина с малки терасовидни къщи за 250 семейства. Костхайм се превръща в селище без ясно изразен център и без ясно разделение между фабриките и жилищните райони.

Промишлени предприятия като MAN, Cellulose и Linde са ориентирани към военните изисквания на войната още преди 1936 г. MAN произвежда части за мостове и корабни корпуси, а Cellulose - основни материали за производството на боеприпаси, униформи, авиационно гориво и медицински консумативи. Втората световна война нанася значителни щети на сградите на имението и Alt Kostheim. Улицата по протежение на Хоххаймерщрасе е почти напълно разрушена. Католическите църкви и настоящият енорийски център в имението са поразени от бомби. По време на въздушните нападения са убити 113 души. След Втората световна война са построени нови жилищни квартали като "Сампел" и са създадени нови промишлени предприятия.

На 25 юли 1945 г. Костхайм е присъединен към Висбаден. През 2003 г. все още има седем малки ферми с площ под два хектара. Освен това има 13 постоянни стопанства (предимно в областта на лозарството, 66 хектара), които обработват общо 191 хектара земя. Днес (към 1 януари 2016 г.) в Костхайм живеят 14 076 души в 6 752 домакинства.

Особеност е ежегодното поклонническо пътуване на енорията на Свети Килиан до Фишбах в Таунус. Според твърдения, които не са документирани, се твърди, че поклонничеството е довело до чудотворния образ в параклиса на Гимбах още през 1444 г. Причината вероятно е бил големият глад. Други източници говорят за времето около 1666 г. - година на голяма чумна епидемия, в която Костхайм е пощаден от епидемията. През 1828 г. поклонението е преместено в енорийската църква във Фишбах по настояване на правителството на херцогство Насау. Католиците от енорията все още правят ежегодно покайно поклонение там.

През 1751 г. върху граничен камък от 1603 г. са открити два кръстосани лозови ножа, гравирани върху него. Под формата на сребърни щипки на червен фон изображението върху граничния камък е избрано за герб на Костхайм.