Korčula je bila naseljena že v času neolitika. V 6. stoletju pr. n. št. je bila na otoku grška kolonija. Takrat se je zaradi obsežnih in gostih gozdov imenovala Korkyra Melaina (Črna Korkyra). Za časa vladanja rimskega cesarja Oktavijana so Korčulo leta 35 pr. n. št. zavzeli Rimljani, leta 555 pa je bila priključena bizantinskemu cesarstvu. V 9. stoletju so otoku vladali Neretljani, nato pa so se večkrat izmenjali: Benečani, bosanski vladarji in dubrovniška republika, od leta 1420 do 1797, pa je bil otok ponovno pod oblastjo Benetk. V času Napoleonovih vojn je bil izmenoma pod avstrijsko, francosko in britansko oblastjo od 1815 do 1918 pa ponovno pod Avstrijo.

Pravljična Korčula je baje bila dom prelepe Kerkyre, junakinje grške mitologije, po kateri je Korčula dobila ime,[navedi vir] dom pa naj bi ji odredil sam bog Posejdon. Tudi svetovni popotnik Marco Polo je imel svoj dom na Korčuli.[navedi vir]