Estepona ja estava habitada durant la prehistòria, s'han descobert eines de sílex i dòlmens al llarg del curs d'Arroyo Vaquero, a l'oest de la localitat. El seu origen és discutit, encara que les últimes hipòtesis, basades en l'existència d'una important ciutat iber amb un port natural, fan pensar a l'oppidum ibèric de Salduba com l'assentament d'època antiga més proper a l'actual localitat d'Estepona. No obstant això, en els últims anys, s'estan trobant restes romanes en el mateix nucli urbà de la localitat, que podrien correspondre a una important vila romana no només d'ús industrial (assalaments) sinó també defensiu.
Ja en època musulmana, es coneix l'existència d'una fortalesa denominada Al-Extebunna, apareixent per primera vegada el topònim que dóna nom a la ciutat. En l'any 1342 hi ha un important combat naval d'una trentena de galeres en aigües d'Estepona. La flota d'Aragó (donada suport per Gènova i Castella s'enfronta amb victòria final, després de la derrota de les naus d'Alfons XI de Castella a l'Estret de Gibraltar. En el segle XV, durant el domini musulmà, els habitants de la vila es neguen a pagar impostos al rei Enric IV de Castella que finalment autoritza una incursió cristiana. Durant 1456 i el següent any, es conquista el castell i el poblat. Estant en plena època de reconquesta, es mana protegir la costa amb la construcció d'un nou poble, l'anterior havia estat pràcticament destruït, i una fortalesa. Amb els Reis Catòlics, Joana la Boja la sotmet sota dependència de Marbella fins a l'arribada de Felip V. Al voltant del mig miler de esteponers reben llavors, en 1729, la carta de vilatge (es conserva a l'ajuntament).
Durant el segle XV fins al segle XIX tot just es registra un augment demogràfic. En els dos últims segles s'estabilitza i comença a créixer lentament fins a finals del segle XX, des de llavors el creixement de la població és important i ràpid.