Ocala ligger nära den gamla platsen för Ocale eller Ocali, en stor Timucua-by och ett stort hövdingadöme under 1500-talet. Staden Ocala lånade idag namnet från byn. Namnet tros betyda "stor hängmatta" på Timucua-språket. Hernando de Soto passerade Ocale under sin berömda resa genom det som idag är sydöstra USA år 1539. Ocale nämns inte i några senare redogörelser; det verkar ha övergivits i kölvattnet av de Sotos attack.
År 1827 byggdes den amerikanska arméns utpost Fort King nära den nuvarande platsen för Ocala som en buffert mellan seminolerna och de vita bosättarna. Fortet fick tjänstgöra under det andra seminolkriget och användes senare som det första domstolshuset för Marion County 1844. Fort King var början på den nuvarande staden Ocala, som grundades 1846. Greater Ocala är känt som "solens rike". Järnvägstrafiken nådde Ocala i juni 1881, vilket uppmuntrade den ekonomiska utvecklingen. Två år senare förstördes stora delar av Ocalas centrum av en brand på Thanksgiving Day 1883. Byggnaderna återuppbyggdes med tegel, granit och stål i stället för timmer. År 1888 var Ocala känt i hela delstaten som "The Brick City".
I december 1890 höll Farmers' Alliance and Industrial Union, en tidig version av Populist Party, sitt nationella möte i Ocala. Vid mötet antog alliansen en plattform som kom att bli känd som "Ocala Demands". I denna plattform ingick bland annat avskaffande av nationalbanker, statliga lån med låg ränta, fri och obegränsad myntning av silver, återvinning av överskottsmark för järnvägar som staten tagit i anspråk, en graderad inkomstskatt och direktval av senatorer i USA. De flesta av Ocala-kraven kom att bli en del av Populistpartiets plattform.
Ocala var ett viktigt centrum för citrusproduktion fram till den stora frysningen 1894-1895.
Under 1900-talet blev Ocala alltmer känt som ett centrum för turism i Florida. Viktiga attraktioner var bland annat Silver Springs Nature Theme Park, vattenparken Wild Waters och det numera nedlagda Six Gun Territory med western-tema, alla i närliggande Silver Springs, Florida. (Se Six Gun Territory Gallery.) Silver Springs är en 350 hektar stor (1,4 km2 ) naturtemapark som omger Silver River, den största artesiska källformationen i världen.
Den första gården för fullblodshästar i Florida skapades av Carl G. Rose 1943. Tidigare, 1916, hade Rose kommit till Florida från Indiana för att övervaka den första asfaltvägen som byggdes i delstaten. När han fick problem med asfalten försökte han arbeta med en av Floridas rikliga resurser: kalksten. Han insåg också att kalkstenen skulle vara en bra näringskälla för att föda upp starka hästar, så han tog en chansning 1943 och köpte mark längs State Highway 200 för 10 dollar per hektar, som blev Rosemere Farm. Året därpå vann en av hans hästar, Gornil, på Tropical Park i Miami, vilket gjorde honom till den första fullblodshäst från Florida som vann ett lopp i Florida. Entreprenören Bonnie Heath, som följde Rose i hälarna, inrättade snart sin egen fullblodsfarm och producerade delstatens första Kentucky Derby-vinnare. Båda dessa män har stora motorvägar uppkallade efter sig i Ocala. Bonnie Heath Farm ägs och drivs nu av hans son Bonnie Heath, III, och hans fru Kim. Rosemere Farm såldes för länge sedan och Ocalas Paddock Mall och Central Florida College byggdes på platsen.
1956 fick marknaden för fullblodshästar i Ocalaområdet ett uppsving när Needles blev den första Florida-häst som vann Kentucky Derby. År 1978 vann Affirmed, född och uppfödd i Marion County, Triple Crown. I dag är Marion County ett av de stora fullblodscentrumen i världen, med totalt över 1 200 hästgårdar och cirka 900 fullblodsgårdar på sammanlagt cirka 77 000 acres (310 km2 ). Ocala är välkänt som världens hästhuvudstad, en av endast fem städer (fyra i USA och en i Frankrike) som enligt handelskammarens riktlinjer får använda denna titel på grundval av de årliga pengar som hästindustrin producerar. Det finns cirka 44 000 arbetstillfällen som skapas genom uppfödning, träning och relaterat stöd som hästindustrin ger upphov till och som genererar över 2,2 miljarder dollar i årliga pengar. Ocala och "Postime Farms" stöder också en av de största hästshowerna i landet. H.I.T.S eller "Horses in the Sun" är ett dressyr- och hopperevenemang som pågår i ungefär två månader och som varje år ger omkring 6-7 miljoner dollar till den lokala ekonomin i Marion County. Det finns över 100 olika raser förutom fullblodshästar, däribland Tennessee Walker, Paso Fino, Morgans, SaddleBreds, Drafts och American Quarter Horse. Andra hästevenemang i området inkluderar cowboyskytte med Florida Outlaws, samt uthålliga ridturer, tunnlopp, "extrema" cowboyevenemang, hopptävlingar, trickshower, parader, dragkamp med mera.
Ocala började växa snabbt på 1970-talet i och med utvecklingen av Interstate 75 och grundandet av Disney World, som ligger cirka 110 km sydost om staden.
Under de sista decennierna av 1900-talet upplevde Ocalaområdet en av de högsta tillväxttakterna i landet för en stad av dess storlek. Befolkningen i Marion County uppgick år 2000 till över 250 000 invånare, vilket är en ökning från under 100 000 år 1975. En stor del av länets tillväxt beror på områdets växande popularitet som pensionärsdestination, främst i två områden sydväst och söder om staden: SR 200-korridoren respektive The Villages.
Många historiska hus finns bevarade i Ocalas stora bostadsområde Historic District, som inrättades 1984. Ett fokus i detta distrikt är East Fort King Street, med många utmärkta exempel på viktoriansk arkitektur. Bland Ocalas byggnader som finns med i National Register of Historic Places finns Coca Cola Building, E. C. Smith House, East Hall, Marion Hotel, Mount Zion A.M.E. Church, Ritz Historic Inn och Union Train Station.
Själva den ursprungliga platsen för Fort King blev ett nationellt historiskt landmärke 2004.