Самые древние следы поселения людей в районе Костхайм относятся к эпохе неолита. В римскую эпоху Костхайм имел стратегическое значение: сначала как военная база для охраны переправы через Майн, затем как плацдарм для стационарного деревянного моста, построенного в 75-110 годах нашей эры и пересекавшего реку к западу от сегодняшней церкви. Армейская дорога из Кастеля в Хеддернхайм также затрагивала деревню; так называемая Штайнернштрассе была ее частью. Многие находки указывают на то, что в Костхайме постепенно возникло римское поселение. Эта эпоха закончилась в 406 году в битве с аланами, суэби и вандалами. С тех пор Костхайм имел большое значение как переправа через реку, и можно предположить, что место римского поселения было захвачено германскими племенами. На это указывает и название местности, которое можно интерпретировать как раннефранкское.

Следующее известие о Костхейме - его первое документальное упоминание в 790 году, когда 31 августа того же года Карл Великий издал два документа в "вилле Копсистайно". Это название происходит от латинского "caput stagni", "голова на болоте". Другие формы названия - "Чуффингстанг", затем "Куфстайн", а с 1217 года - "К(х)остхейм". Патронаж над местной церковью Святого Килиана, а также десятина принадлежали майнцскому женскому монастырю Альтмюнстер, который был самым важным землевладельцем в Костхайме. Это включало в себя назначение и оплату труда местного священника и звонаря; монастырь также отвечал за содержание здания церкви. Монастырь Альтмюнстер также владел паромом через Майн, который он сдал в аренду костгеймским паромщикам в 1432 году; он также сдавал свои земли в Костгейме другим церковным учреждениям. Вероятно, у лордов Эппштайна также была своя усадьба в Костхайме. Однако трудно отделить его от бейливика над Костхеймом, который они получили в качестве вотчины еще в XII веке и осуществляли с помощью уполномоченных суб-бейлифов. Центральной церковной властью был архидиаконство настоятеля собора Святого Петра в Майнце, Кастельское деканатство.

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

Округ Костхайм простирался до Гинсхайма на левом берегу Майна и до Хоххайма, Делькенхайма, Эрбенхайма и Кастеля на правом берегу. До 1528 года Костхайм был одним из мест с разделенным местным и судебным правлением: местное правление осуществлял Святой Стефан в Майнце, а судебное - лорды Эппштайна в качестве судебных приставов. Когда в 1492 году они продали Костхайм ландграфам Гессенским, те, среди прочих, сохранили за собой бейливик, пока не продали его архиепископу Майнца в августе 1528 года. В том же году в Вейстуме были регламентированы обязанности главного и подглавного клерка, биделя, землемера и т.д. Также были подробно описаны обязанности приходского священника святого Килиана и его звонаря, который был одновременно органистом и директором школы. Впервые школа упоминается около 1500 года. Под властью Майнца Костхайм оставался католическим, хотя Реформация нашла в деревне своих сторонников. Костхайм был сожжен в 1552 году.

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

Уже в средние века Костхайм был окружен городской стеной с верхними воротами на Брухштрассе и нижними воротами на Майне. Планировка улиц Матильденштрассе, Маргаретенштрассе и Херренштрассе (где жили лорды Святого Стефана) до сих пор напоминает о средневековых постройках. Ежегодно избираемые Летцмейстеры отвечали за безопасность ворот и стен.

В XV веке Костхайм был зажиточной деревней, о чем свидетельствует Зальбух, в котором записаны феодальные повинности. Амбар на углу Херренштрассе и Бургштрассе - остаток десятинной фермы. В XVIII веке здесь процветали сельское хозяйство и виноградарство. В 1758 году школа была отмечена особыми похвалами в школьной статистике. Во главе администрации в XVIII веке стояли главный судебный пристав и заместитель судебного пристава.

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

В 1808 году по просьбе костгеймского священника Рёсслера Наполеон предоставил Костгейму 25 лет освобождения от налогов, что побудило священника Генриха в 1821 году прочитать панихиду по умершему французскому императору вопреки запрету государя и церкви. В 1809 году после сильного пожара была построена так называемая Нойдорфхе. Деревня была отстроена заново; к 1830 году в "деревне" Костхайм снова насчитывалось 202 дома с 1 272 жителями, а в 1836 году была освящена новая церковь Килианскирхе.

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

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

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

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

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

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

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

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