Ostaci najstarijeg stanovništva koje je živjelo na prostoru Vele Luke najbolje su proučeni u obližnjoj Veloj spilji (detaljnije: Vela Spila). Ovaj značajan lokalitet, smješten na brdu Pinski rat neposredno iznad uvale Kale, naseljen je već krajem starijeg kamenog doba, približno 20 000 pr. Kr., a iz tih slojeva potiču deseci kamenih strugača, grebača, noževa i drugih alatka korištenih u lovu na životinje poput crvenog jelena, divljeg goveda ili bizona.
Srednje kameno doba obilježeno je životom veće skupine sakupljača morske hrane pa se u naslagama mogu naći tisuće ljuštura priljepaka, kamenica, konjskih kopita, ali i kosti ptica, jelena, lisice drugih životinja lovljenih radi mesa i krzna. Ukopi troje djece svjedoče o duhovnom životu i dosad su najstariji ljudski ostaci nađeni na ovom dijelu Jadrana.
Mlađe kameno doba (neolitik) započinje oko 6 200 god. pr. Kr. impresso kulturom obilježenom nalazima keramičkih posuda ukrašenih utiskivanjem oboda školjke cardium. U to vrijeme je i pripitomljavanje prvih životinja, početak poljoprivrede, otkriće keramike, obrada kamena glačanjem itd.
Srednjim neolitikom koji počinje oko 5 500 god. pr. Kr. dominira kultura koja je prvi put otkivena i proučena u Veloj spilji pa nosi ime Velolučka kultura, a njeno glavno obilježje je primjena bojanih slikanih ukrasa poznatih na istovremenim nalazištima susjedne Apulije.
Hvarska kultura izvrsno je zastupljena s oko 250 000 ulomaka uglavnom crnopolirane i ukrašene keramike te velikom količinom kremenih i koštanih alatka, a u tom razdoblju datiramo ukope muškarca i žene u Veloj Luci poznatih kao "baba i dida". Kraj hvarske kulture zadire duboko u bakreno doba (eneolitika) pa možemo govoriti o jednoj eneolitičkoj fazi hvarske kulture.
Treći milenij pr. Kr. vrijeme je kada dolazi do velikih gibanja i promjena stanovništva. Pojedine nove grupe zastupljene su tek s ponekim predmetom, a neke poput tzv. nositelja žljebljene keramike, pripadnika ljubljanske i cetinske kulture nastanjuju Velu spilju sve do sredine brončanog doba.
Novi stanovnici poznati pod imenom Iliri u prvom i drugom mileniju pr. Kr. žive na vrhovima brda okruženi kamenim suhozidovima, u stalnom strahu od sukoba i vazda spremni braniti svoj skromni imutak, prije svega stoku. Njihova naselja su Glavica u Gradini sv. Ivana, vrh Grebena, Maslinovik, Kopila i još tridesetak položaja diljem Korčule. Svoje pokojnike ukapaju u kamenim gomilama, smještenim obično na vrhovima brda, a otokom će vladati sve do 30 god. pr. Kr. kada ih konačno pobjeđuje vojska rimskog vladara Oktavijana Augusta.
Rimski legionari naselili su širu okolicu Vele Luke donoseći u ove krajeve kulturu, pismenost i način života uobičajen duž svih sredozemnih obala. Njihove čvrste i prostrane kamene kuće bili su središta razvijenog gospodarstava, a proizvodili su velike količine žitarica, ulja, vina, soljene ribe i drugih namirnica, koje su se intezivno razmjenjivale pa je i do nas došao dio onovremenih luksuznih predmeta. Gospodarska zdanja tzv. villae rusticae redovito su opremane sustavom za centralno grijenje, a ukrašene mozaične podnice, dobro izrađeni kapiteli pa i raskošne grobnice opremljene kvalitetnim nadgrobnim pločama svjedoče o razini kvalitete života u prvim stoljećima nakon Krista. Lokacije ovoh objekata su Poplat - pored crkve od Karmena, Potirna - Mirje, Gudulija - iznad tvornice Elra, Rododma, Zablaće - pored crkve Sv.Kuzme i Damjana, Bradat - Mirje, otočić Gubeša, dvije lokacije u polju Vrbovica itd.
Antička civilizacija počinje propadati već od trećeg stoljeća, trgovina zamire, a villae rusticae se napuštaju ili pretvaraju u manja seoska središta. U to doba se na naše obale širi nova vjera - kršćanstvo, čije je postojanje zasvjedočeno nizom manjih crkvica. Postojanje kršćanskih bogomolja zasigurni je potvrđeno na Glavici poluotoka Gradina, a vjerojatno i na spomenutoj lokaciji Gudulija - Beneficij.
Rani srednji vijek je razdoblje iz kojeg praktički nemamo sačuvanih ostataka objekata ili pisanih dokumenata. Ipak poznato je da od osmog vijeka otok pa i prostor Vele Luke naseljavaju Neretljani, koji svojim lađama stoljećima vladaju Jadranom boreći se za prevlast s Mlečanima. Arhivski izvori su vrlo škrti, pa je malo zapisa o sukobima s normanskim, saracenskim, turskim i drugim pljačkaškim skupinama. Oskudne tragove nalazimo u Korčulanskom statutu iz 1214. god. i u nekoliko isprava. Nešto više vijesti nalazimo tek od kraja 16. stoljeća, kada je turska opasnost dijelom otklonjena pa se život vraća u predjele pored mora. Sigurnosti radi grade se kuće - utvrde (kašteli), a dosad su poznate one obitelji Ismaeli (ex Joković) iz 1490. god., kaštel Gabrijellis, Nikoničić - Kanavelić i Kolović - Šantić.
Razvitak suvremene Vele Luke počinje krajem 18. stoljeća. U to vrijeme buđenje trgovine i prometa rezultira stalnim naseljavanjem stanovnika okolnih zaseoka i "stanova" u dnu velolučkog zaljeva u široj okolini crkvice sv. Vičenca i ranije sagrađenih kaštela. Razvitak naselja bio je vrlo intezivan, već 1819. god. usprkos protivljenju susjednog naselja Blata, Vela Luka dobiva kapelu, 1828. i seoskog glavara. Selo u to vrijeme broji 109 obitelji pa započinje borba za izgradnju župne crkve i osamostaljenje od matičnog naselja Blato. Ta nastojanja su uspješno okončana burne 1848. god. kada je, prije svega zahvaljujući sposobnom velolučkom kapelanu don Petru Jokoviću, sagrađena župna crkva sv. Josipa i konačno 1849. god. oformljena samostalna župa.(detaljnije: Župa Vela Luka)
Daljnji razvitak bio je ubrzan. Redovita pučka škola započinje sa radom 1857. god., pošta je otvorena 1885. god., parni mlin je proradio 1892. god. kada i suvremeni uređaj za preradu maslina, 1898. god. sagrađena je prva tvornica ribljih konzerva. Konačan proces osamostaljenja naselja okončan je 1898. god. formiranjem samostalne političke općine Vela Luka. Broj stanovnika je također ubrzano rastao, 1857. god. je oko 1200 stanovnika, 1880. god. on iznosi 1956 ljudi, 1900. god. je čak 3555 stalno naseljenih, 1910. god. 4334, 1921. god. 4995, 1931. god. 4038 itd.
U drugoj polovini 19. st. gospodarstvo Vele Luke je ovisilo prvenstveno o izvozu vina u ostale djelove Austro-Ugarske, a u manjoj mjeri na ribarstvu, preradi ribe, trgovini i pomorstvu.
Vinska klauzula 1891. god. zaustavlja prosperitet, a jedan od izlaza iz bijede je sve češće iseljavanje u prekomorske zemlje..
Kulturni razvitak istovremen je sa širenjem narodnjačke misli i osnutkom brojnih udruga poput Crkvenog pjevačkog zbora 1891. god., Veloluške glazbe 1893. god., čitaonice Hrvatski preporod 1894. god. i pjevačko-tamburaškog društva Hum 1909. god.
Naglu demografsku ekspanziju Vela Luka bilježi na prijelazu 19. u 20. st., ali porast broja stanovnika nije popraćen jačanjem gospodarstva, naprotiv nazadovanje poljoprivrede, prije svega kriza vinogradarstva, dovodi do siromaštva i iseljavanja u prekomorske zemlje.
Prvi svjetski rat nije posredno zahvatio Velu Luku, ali ratna događanja samo pojačavljaju siromaštvo i neimaštinu. Kratkotrajna talijanska okupacija nakon rata i raspada Austro-Ugarske završena je pripajanjem Korčule Kraljevini SHS.
Od 1898. god. Vela Luka je samostalna općina s općinskim grbom modre boje na kojem je bijela golubica sa maslinovom grančicom u kljunu. Prvi načelnik bio je Tadija Tabain-Šantić.
Dan Općine slavi se na blagdan sv. Josipa, 19. ožujka, kome je posvećena i župna crkva. O granicama Općine, od njenog osnutka, postoji spor sa susjednim naseljem Blatom, koje permanentno pokazuje pretenzije prema predjelu Potirna.
U razdoblju između dva svjetska rata stanovništvo je gotovo potpuno okrenuto ekstenzivnoj poljoprivredi, posebno vinovoj lozi, a sve ostale sredozemne kulture su sporedne. U potrazi za plodnom zemljom iskrčeni su deseci kilometara terasa koje još uvijek, iako napuštene, dominiraju krajolikom. Maslinarstvo i proizvodnja ulja tek pred II. svj. rat doživljavaju ekspanziju da bi danas predstavljali temelj otočke poljoprivrede, a količinama i kvalitetom zauzimaju značajan udio proizvodnje i na razini Hrvatske.
Tijekom II. svj. rata stanovništvo Vele Luke se na razne načine priključuje antifašističkom pokretu. Razlog tome su okupacije Talijana od 1941. do 1943. god. i Njemaca od kraja 1943. god. do 22.travnja 1944.god. Pred okupaciju Vele Luke od strane njemačkog agresora dobar dio Velolučana (staraca, žena i djece) otišao je u zbjeg zajedno sa ostalim stanovnicima susjednih otoka i priobalja u daleki El Shatt. Otpor osvajaču "plaćen" je sa 284 života poginulih i umrlih, uglavnom mladih ljudi, te stotinama ranjenih i invalida, znatnim materijalnim štetama i svim oblicima razaranja.
Vrijedno je također istaći da su tijekom II. svj. rata utočište u Veloj Luci pronašli progonjeni Židovi. Bilo ih je nekoliko stotina.
U spomen na sve pale Velolučane u II. svj. ratu Velolučani su u centru mjesta podigli spomenik, rad akademskog kipara Mirka Ostoje.
Za razliku od predratnog poljoprivredno-ribarskog naselja, Vela Luka u prvim desetljećima nakon II. svj. rata razvija i industrijsku djelatnost. Godine 1948. utemeljeno je brodogradilište "Greben". 1956. god. pokrenuta je Obalna plovidba. Tvornica za preradu ribe "Jadranka" utemeljena 1892. god., kasnije dobiva nove proizvodne pogone, a u njenoj staroj zgradi pokreće proizvodnju Tvornica limene ambalaže. U posljednjim desetljećima 20. stoljeća producira se oko tisuću kreveta u hotelskim objektima, još toliko u privatnom smještaju, osniva se lječilište "Kalos", gradi se Dom umirovljenika, proizvodnju pokreće Tvornica elektronskih uređaja, osuvremenjuje se trgovina, poljoprivredna proizvodnja, a snažan zamah dobijaju i društvene djelatnosti. Posljednjih desetljeća prošlog stoljeća probijeno je i uređeno na desetke kilometara ceste, poljskih puteva i šumskih "prosika". Od infrastrukturnih zahvata vrijedno je spomenuti izgradnju vodovoda i trajektnog pristaništa. Sagrađen je novi Dom zdravlja, Srednja škola, Centar za kulturu, Zadružni dom sa kinom, zgrada Općine, nekoliko sportskih objekata, te niz pratećih sadržaja. Nažalost, opća kriza i problemi tranzicije izraženi u 90-im godinama nisu mimoišli ni Velu Luku.
Uloga Vele Luke u domovinskom ratu tek će biti predmet ozbiljnih analiza, a zasad treba zabilježiti da je prvi brod HRM predan od strane brodogradilišta "Greben", te značajnu ulogu velolučkih topnika u borbi protiv "Jugo" mornarice u korčulanskom kanalu 16. 10. 1991. Više stotina Velolučana aktivno je sudjelovalo u Domovinskom ratu. Najveći broj je bio na južnom bojištu, te su dali veliki doprinos u obrani i oslobađanju hrvatskog juga.
Danas je Vela Luka značajno prometno, gospodarsko, kulturno i turističko središte okrenuto budućnosti i nadi u vlastiti napredak. Oko 4400 stanovnika ovog dalmatinskog otočkog naselja nastoji zadržati postignuti društveni i osobni standard razvitkom, čiste industrije, poljoprivrede, uslužnih djelatnosti, a prije svega turizma, te osigurati bolji život i opstanak na otoku.