Kadıköy'ün kuruluşu İstanbul'un kuruluşundan çok eski yıllara dayanır. Fikirtepe'de 1942 ile 1952 yılları arasında yapılan kazılarda MÖ 3000 yıllarına ait aletler ve insan iskeletleri bulunmuştur. Ayrıca balık, köpek, koyun, keçi kemiklerine rastlanmıştır. Bulunan araçlar arasında taştan çekiç, kemik, keramik, taş ağırşakları, bronz eserler, inci taneleri, firuze taşından eserler de vardır. Moda Burnu'nda Kalkedon kentinde Fenikelilerden kalma kandiller, vazo kırıkları, öküz heykeli, pişirilmiş balçıktan sakallı erkek başı, Kalkedonya Kitabesi'nin yazıldığı bronz levha bulunmuştur.
Kadıköy İskele Meydanı'ndaki Atatürk Anıtı

    Fikirtepe'deki Karhadon, Moda Burunu'ndaki Kalkedon şehirleri, Fenikelilerin Karadeniz kıyılarında kurdukları şehirlere hareket ermek için durma, gereksinimlerini tamamlama merkeziydi.

    İyonya'dan (Anadolu'nun Ege Denizi kıyılarından) gelen ve Yunanistan'a inen Akaların bir kolu M.Ö 675 yıllarında Fikirtepe ve Moda'daki iki Fenike şehrini aldı. Bugün Bahariye, Mühürdar, Moda semtlerinin bulunduğu yerlere yerleştiler. Kalkedon şehrini genişlettiler. Kısa süre içinde İzmit'e kadar olan bölgeyi el geçirdiler. Buralarda Kalkedon Devleti'ni kurdular. Anadolu'nun içlerinden gelenleri bu topraklara yerleştirdiler. Başkent Kalkedon (Kadıköy) oldu. Ülkenin adına Kalkedonya deniyordu. Kalkedonyalılar savaşçı ve uygarlıkta ileriydiler.

    Kalkedonyalılar bugünkü Haliç'in Unkapanı'yla Eyüp arasında oturan Traklarla, Fenike şehirleriyle, İzmit'teki Bitinyalılarla, Bergama Devleti'yle ticaret yaparlardı.

    Haydarpaşa Deresi'nin düzlüklerinde hipodromları, tapınakları vardı. MÖ V. yüzyılda Kral Periyut, "talen" adı verilen madeni paralar çıkardı. Kalkedonyalılar şehrin savunmasını da düşünmüşlerdi. Perslerden, Bitinyalılardan, Gotlardan korunmak için Haydarpaşa çayırıyla Kuşdili çayırı arasında bir hisar yapmışlardı. Sonradan doğudan ve batıdan gelenler buradaki surları ve eserleri yıktılar.

    Kalkedonyalılar cam eşya, altından küpe, yüzük gibi süs eşyası yapmasını ve mermeri işlemesini iyi biliyorlardı. Şehirlerinin kapısına "Khalkedon" yazılı kitabeler asarlardı.

    M.Ö 658 yıllarında Yunanistan'ın Korent kanalı dolaylarından kurtulmak, daha verimli topraklarda yaşamak için kendilerine yeni bir yurt aradılar. Delf Tapınağı'nın kâhini, Megara Kralı Vizas'a "Körler ülkesinin karşısındaki yerler size yurt olacak." dedi.

    Kral Vizas halkıyla birlikte yurt aramaya çıktı. M.Ö 650 yılında Sarayburnu'na geldi. Sarayburnu'ndan etrafına bakınca buranın güzelliğine şaştı. Kalkedonyalıların bu kadar güzel, bu kadar yaşamaya elverişli yeri göremeyip boş bıraktıklarına göre kör olması gerektiğini düşündü ve kâhinin dediği, körler ülkesinin karşısındaki yer burasıdır diye Sarayburnu'nda konakladı. M.Ö 608'le 600 yılları arasında Sarayburnu'nda kendi adını verdiği "Bizans" şehrini kurdu.

    Pers Kralı Dârâ (Darius) İskitlerle savaşa giderken Kalkedonya'yı da aldı. Bunun üzerine Kalkedonyalılar Bizanslılarla birlik olarak Dârâ'ya karşı savaştılar. Dârâ, Kalkedonyalıların evlerini, tapınaklarını, kentlerini yaktı, yıktı. Dârâ, Fenikelilerle birlik oldu. Kalkedonyalılar önce İyonlarla, sonra Bizanslılarla birleşip yeniden savaşa tutuştular. Kalkedonyalılar savaş alanını bırakıp kaçtı. Fenikeliler donanmalarıyla Bizanslılara saldırdı, Kalkedonya'yı yakıp yıkarak ele geçirdiler.

    Kalkedonya Perslerin eline geçmişti. Makedonya Kralı İskender, Persleri yenip Pers kentleriyle birlikte Kalkedonya'yı da aldı.

    M.Ö 281 yılında Bitinyalılar Marmara kıyılarındaki kentlerin çoğunu ellerine geçirdiler. Kalkedonya'yı da aldılar. Kalkedonya bir ara özgür kalmışsa da çok geçmeden Romalıların yönetimine girdi. Makedonya Savaşı sırasında Kalkedonyalılarla Romalılar anlaştılar. Romalılar Kalkedonyalılara savaş gemileri göndererek askeri yardım yaptılar.

    Kalkedonya 561 yılının 21 Mart'ında Arapların saldırısına uğradı, 667 yılında Araplar yeniden İstanbul kıyılarında görüldüler. Kıyı kentlerinden birçok tutsak alıp ülkelerine döndüler.

    Haçlı savaşlarında da haçlı orduları birkaç kez Kalkedonya'yı çiğnediler.

    781 yılında Abbasi Devleti Halifesi Harun Reşit'in komutanlarından Malatyalı Battal Gazi Kalkedonya'yı aldı. Bu tarihten sonra Kalkedonya adı yerine Gaziköy adı kullanılmaya başlandı.

    Kutalmışoğlu Süleyman Şah 1080 yılında Kalkedonya'yı Anadolu Selçuklu Devleti'ne kattı. Fakat bir süre sonra son kez Bizanslıların eline geçti. 1096 yılında Haçlı orduları Kalkedonya'dan Asya'ya geçtiler. Daha sonra dördüncü Haçlı orduları 1204'te Kalkedonya'yı İstanbul'la birlikte işgal ettiler. Yakıp yıktılar, yağmaladılar, anıtlardaki değerli madenleri söktüler.