Ang Kuala Lumpur, na orihinal na maliit na nayon, ay itinatag noong kalagitnaan ng ika-19 na siglo bilang resulta ng umuusbong na industriya ng pagmimina ng lata.Naakit ng rehiyon ang mga Chinese na minero, na nagtayo ng mga minahan sa paligid ng Ilog Selangor, at mga Sumatran na nagtayo ng kanilang sarili sa lugar ng Ulu Klang.Ang bayan ay nagsimulang magkaroon ng hugis sa paligid ng Old Market Square, na may mga kalsada na umaabot sa iba't ibang lugar ng pagmimina.Ang pagtatatag ng Kuala Lumpur bilang isang makabuluhang bayan ay dumating noong mga 1857 nang si Raja Abdullah bin Raja Jaafar at ang kanyang kapatid, na may pondo mula sa mga negosyanteng Intsik ng Malaccan, ay gumamit ng mga Chinese na minero upang magbukas ng mga bagong minahan ng lata.Ang mga minahan na ito ang naging buhay ng bayan, na nagsilbing koleksiyon at dispersal point ng lata.Sa mga unang taon nito, nahaharap ang Kuala Lumpur ng ilang hamon.Ang mga kahoy at 'atap' (palm frond thatched) na mga gusali ay madaling masunog, at ang bayan ay sinalanta ng mga sakit at baha dahil sa heograpikal na posisyon nito.Bukod dito, ang bayan ay nasangkot sa Digmaang Sibil ng Selangor, na may iba't ibang paksyon na nag-aagawan para sa kontrol sa mga mayamang minahan ng lata.Ang mga mahahalagang tao tulad ni Yap Ah Loy, ang ikatlong Chinese Kapitan ng Kuala Lumpur, ay gumanap ng mga mahalagang papel sa mga magulong panahong ito.Ang pamumuno ni Yap at ang kanyang alyansa sa mga opisyal ng Britanya, kabilang si Frank Swettenham, ay nag-ambag sa pagbangon at paglago ng bayan.Ang impluwensyang kolonyal ng Britanya ay naging instrumento sa paghubog ng modernong pagkakakilanlan ng Kuala Lumpur.Sa ilalim ng British Resident na si Frank Swettenham, ang bayan ay sumailalim sa makabuluhang pagpapabuti.Ang mga gusali ay ipinag-uutos na gawa sa ladrilyo at baldosa para sa paglaban sa sunog, pinalawak ang mga kalye, at napabuti ang kalinisan.Ang pagtatayo ng isang linya ng tren sa pagitan ng Kuala Lumpur at Klang noong 1886 ay higit na nagpalakas sa paglago ng bayan, kung saan ang populasyon ay lumaki mula 4,500 noong 1884 hanggang 20,000 noong 1890. Noong 1896, ang katanyagan ng Kuala Lumpur ay lumago kaya napili ito bilang kabisera ng bagong tatag na Federated Malay States.