L'origine del nome Corleone è incerta, e ha subito diverse modificazioni: da un ipotetico greco-bizantino χώραλέων (chó̱raléo̱n, il "paese di Leone" composto da chó̱ra, "paese" nel senso di territorio e da léo̱n, "Leone" come nome personale) all'arabo Qurlayun (Kurulliùn قُرَّ العَيْون tradotto dall`arabo significa: "il posto che ci rende estremamente felici solo a guardarlo") durante l'Emirato di Sicilia, dal latino Curilionum al normanno Coraigliòn, dall'aragonese Conillon, fino alle forme italiane ormai desuete Coriglione e Coniglione, dal quale è derivato il siciliano Cunigghiuni. La forma Corleone è attestata dal 1556, ma fino a tutto l'Ottocento è ancora in uso la forma più antica Coriglione.
Età antica
Il territorio di Corleone risulta frequentato sin dalla preistoria. Ricerche hanno individuato numerosi insediamenti distribuiti attorno a due poli principali: Pietralunga e "La Vecchia". Tale nome fa riferimento ad una montagna che si erge per circa 1000 s.l.m. e dista circa due km dall'odierno centro abitato. Il sito di Pietralunga risulta occupato dal neolitico finale a tutta l'età del bronzo (presenza di un bicchiere campaniforme decorato a pointillè) mentre il sito della "La Vecchia", il cui toponimo sottintende il termine "città" piuttosto che "montagna", come ha del resto intuito il Traselli, fu abitata sin all'età medioevale (presenza di un imponente castello con torrioni aggettanti, recentemente individuato), anche se l'insediamento più consistente è riferibile a epoca arcaica e classica. "I pochi materiali riferibili ad età ellenistica rinvenuti nel sito hanno supportato l'ipotesi dell'identificazione dell'antico centro abitato posto sulla Vecchia con la Schera di Cicerone, Cluverio e Tolomeo, anche se tuttora troppo labili sono i resti archeologici su cui si basa tale teoria" (D'angelo - Spatafora).
Età medievale
Il nome Corleone è attestato come Corilioni in un atto notarile del 1326 scritto in latino medievale.
In età medioevale La Vecchia costituì l'alterego della città di Corleone e fu probabilmente rifugio ideale dei musulmani ribelli del distretto, poi deportati a Lucera in Puglia nel 1225 con le sanguinose repressioni di Federico II. Nel 1080 veniva conquistata dai Normanni e nel 1095 fu annessa alla diocesi di Palermo. Circa cento anni dopo fu annessa alla nuova diocesi di Monreale. La città già infeudata nel 1180 alla chiesa di Monreale, venne ripopolata nel 1237 da una colonia di ghibellini Lombardi guidata da Oddone de Camerana, per concessione fatta a Brescia dallo stesso imperatore.
Tuttavia nel 1249 Federico, revocando il precedente privilegio, assegnava la città al regio demanio, anche se il flusso migratorio degli abitanti della Pianura Padana continuò fino alle soglie dei Vespri siciliani. Il che è dimostrato da un documento edito da Iris Mirazita, con il quale “il nobilis Corrado de Camerana, su incarico della curia di Corleone assegna agli uomini che verranno ad abitare a Corleone casalinis pro faciendis dominibus”, i cui nomi lasciano supporre l'origine settentrionale e latina. Un altro Camerana, di nome Bonifacio, si distinse nella rivoluzione dei Vespri siciliani capitanando l'insurrezione antiangioina di circa tremila corleonesi, accorrendo per primo in soccorso alla città di Palermo, tanto che il senato palermitano definì Corleone “soror mea”.
Durante il regno di Federico IV di Sicilia, detto il semplice, la città si ribellava alla corona ma veniva riconquistata nel 1355. Nuovamente perduta veniva assediata dal Ventimiglia nel 1358. Durante il governo dei quattro vicari la città entro nell'area di influenza della potentissima famiglia Chiaramonte ma nel 1391 fu donata dalla regina Maria di Sicilia a Berardo di Queralt, canonico di Lerida, senza che tuttavia questi ne prendesse mai possesso. Quindi fu occupata da Nicola Peralta figlio del vicario Guglielmo, ma il re Martino il Giovane la restituì al regio demanio, confermandone i privilegi 1397 e concedendo alcuni sgravi fiscali.
Età moderna
Nel marzo del 1434 il re Alfonso il Magnanimo si recò di persona a Corleone e nell'occasione concedette alcune gabelle al beneficio della città con lo scopo di restaurare le mura e fare fronte alle necessità, promettendo altresì l'inalienabilità della città alla quale concedeva il titolo di “Animosa Civitas”. Tuttavia Corleone nel 1440 fu venduta a Federico Ventimiglia per 19000 fiorini, con riserva di riscatto in qualsiasi momento. La concessione veniva revocata nel maggio 1447 dallo stesso re Alfonso per essere rifatta nello stesso anno ad un certo Giovanni di Bologna. Nel 1452 la città veniva infine concessa all'avvocato Giacomo Pilaya.
Nel 1516 Corleone aderì ai moti rivoluzionari della città di Palermo contro il viceré Moncada. La rivolta Corleonese, capitanata da un ceto Fabio La Porta, assunse caratteri prettamente popolari ed ebbe come scopo la richiesta di sgravi fiscali. Venne tuttavia repressa nel sangue dalle truppe del viceré guidate dal vicario generale Gerardo Bonanno. Verso la fine dello stesso secolo le condizioni sociali della città si aggravarono ulteriormente. La peste del 1575-77 e la carestia del 1592 furono infatti causa di lutti e di desolazione. Il 3 giugno del 1625 Corleone fu venduta, assieme ad altre città demaniali come Agira, Calascibetta ecc., ad alcuni mercanti genovesi, dai quali si riscattò dietro pagamento di 15200 once. Le condizioni di vendita erano state tuttavia assai gravi perché prevedevano la facoltà di “poterle vendere in feudo coi suoi uomini, vassalli, feudi e sub-feudi con la giurisdizione di prima, seconda e terza istanza civile, criminale e mista, mero e misto impero”.
Nel 1649 la città veniva ancora una volta messa in vendita dalla corona in cerca di denaro per il riassestamento della flotta spagnola. Fu quindi acquistata per 16400 once dal giurisperito corleonese Giuseppe Sgarlata, il quale poi accettò il riscatto dietro il pagamento di una rendita di 820 once a ragione del 5% sul capitale impegnato e ricevendo il titolo di Marchese di Chiosi al posto di quello di Marchese di Corleone. I cittadini corleonesi che tenevano particolarmente ai loro privilegi derivati dal fatto che la città fosse demaniale (ovvero governata da un patriziato espressione della nobiltà cittadina e non soggetta a un barone), ricomprò sempre la propria libertà ogni volta che il sovrano vendette la città. Corleone era la città più importante dell'entroterra della Sicilia occidentale e godeva di molti privilegi tra i quali il "mero e misto imperio", ovvero la possibilità di gestire la giustizia in loco e altri che la esentavano da alcune gabelle e che consentivano (caso unico in Sicilia) che il capitano della città fosse un corleonese e non un forestiero. Come le più importanti città demaniali della Sicilia, Corleone aveva un Senato cittadino (titolo riconosciuto nel 1816 da Ferdinando I delle Due Sicilie ma già in uso da almeno due secoli).
Alla carica di Senatore potevano essere ammesse solo le famiglie dell'aristocrazia (Ansalone, d'Anna, Bentivegna, Bruno, Cannarozzo, Canzoneri, Catinella, Crescimanno, Firmaturi, Garlano, Maringo, Palazzo, Pittacoli, Sangiorgi, Sarzana, Valenti ecc.). Corleone inoltre era famosa per l'ottima qualità del vino prodotto nel suo territorio, aveva una "borsa del grano" ed era considerata il "granaio della Sicilia" essendone grande produttrice. Si può affermare che in età moderna la città fosse molto ricca, con alcuni dei suoi cittadini estremamente agiati, molto sviluppata da un punto di vista economico ma anche sociale, culturale e artistico, basti pensare alla grande quantità di maestranze di ottimo livello che edificavano chiese, conventi e che decoravano con grande maestria e alto livello artistico palazzi anche nel resto della Sicilia.
Età contemporanea
Con la cacciata dei Gesuiti dal Regno di Sicilia a partire dal 1767 voluta da Carlo III e dal marchese Bernardo Tanucci suo ministro e noto anticlericale, anche a Corleone ci furono grossi cambiamenti. La Compagnia di Gesù, infatti, era proprietaria della stragrande maggioranza dei feudi e dei latifondi del territorio corleonese, la loro cacciata e conseguente confisca dei beni permise ad ambiziosi imprenditori di acquistare decine di ettari di terreni. Questi nuovi baroni settecenteschi, i maggiori dei quali furono i Bentivegna, i Cammarata, i Canzoneri, i Patti e i Paternostro, diedero una spinta decisiva all'economia locale grazie alla loro intraprendenza. Questi infatti adottarono subito nuove tecniche agricole, cosa rara in Sicilia dove i baroni ma anche gli stessi contadini e mezzadri preferivano tecniche di coltivazione oramai obsolete. Sotto questa nuova spinta economica, si ebbe la costruzione di nuove dimore baronali molto pregievoli che oggi, a causa degli abusi edilizi, non sono del tutto visibili.
Corleone contribuì ai fatti risorgimentali con l'azione rivoluzionaria di Francesco Bentivegna, il quale dopo aver partecipato ai moti del 1848, capitanò un'insurrezione antiborbonica nei comuni del circondario finché fu arrestato e quindi fucilato a Mezzojuso il 20 dicembre 1856. Il 27 maggio 1860 la città fu teatro di una furiosa battaglia tra la colonna garibaldina guidata dal colonnello Vincenzo Giordano Orsini e il grosso dell'esercito borbonico a comando del generale svizzero Von Meckel, sviato da Palermo con uno stratagemma ordito dallo stesso Garibaldi. In quella occasione si formò una squadra di volontari (picciotti) la quale, capitanata da Ferdinando Firmaturi, si unì ai garibaldini nella marcia verso Palermo.
Il secolo XIX si concludeva con l'azione sociale di Bernardino Verro, uno dei capi del movimento dei fasci siciliani, il quale, dopo aver fondato il 3 aprile 1893 il Fascio di Corleone, fu l'ideatore dei nuovi Patti Agrari che vennero stipulati tra contadini e gabelloti nel congresso agricolo siciliano del 30 luglio 1893, tenutosi a Corleone tanto che la città cominciò ad assumere il titolo di “Capitale Contadina”. Il 13 settembre 1893, a seguito della trattativa tra Bernardino Verro e Gaetano Palazzo Dara, che rappresentava i proprietari Marchese Carlo Sarzana di Sant'Ippolito, Avvocato Nicolò Provenzano e Angelo Streva, fu concluso il primo contratto quale "Patti colonici stabiliti dall'arbitrato per lo sciopero 1893-1894, tra il Fascio dei Lavoratori di Corleone ed i signori Streva Angelo e Palazzo Gaetano".
Alla Grande Guerra Corleone contribuì con 105 morti sul campo e numerosi feriti. Tra gli altri servitori della patria si distinsero il capitano Guglielmo Triolo, più volte medaglia d'argento al valore, e l'ardimentoso generale Vincenzo Streva (1870 – 1949) passato da Adua al fronte austriaco. Il seme sociale di Bernardino Verro sarebbe germogliato a Corleone ancora una volta nel secondo dopoguerra, con la nascita del movimento contadino per l'occupazione delle terre incolte, capeggiato dal sindacalista Placido Rizzotto, ucciso dalla mafia.
A partire dal secondo dopoguerra, Corleone è diventata tristemente nota per aver dato i natali ad alcuni pericolosi banditi e mafiosi (tra cui spiccavano Michele Navarra, Luciano Liggio, Bernardo Provenzano, Salvatore Riina e i fratelli Calogero e Leoluca Bagarella), i quali si resero protagonisti di violenti e sanguinosi episodi di cronaca nera che sconvolsero l'opinione pubblica siciliana ed italiana dell'epoca. Legato alla cosca corleonese era anche il sindaco di Palermo Vito Ciancimino, nato a Corleone.