Sofia var från början en thrakisk bosättning kallad Serdica, namngiven efter den thrakiska grenen Serdi. Runt 500 f.Kr. bosatte sig en annan gren i regionen, Odrysi, känd som personer (ethnos) med sina egna kungadöme. Under en kort period under 300-talet f.Kr. tilldelades staden till Filip II av Makedonien och hans son Alexander den store.

Runt år 29 erövrades staden av romarna och fick namnet Ulpia Serdica. Den blev ett municipium, eller center för en administrativ region, under kejsare Trajanus (98-117) regeringstid. Det första skrivna omnämnandet av Serdica gjordes av Klaudios Ptolemaios (runt år 100). Staden utvidgades, med små torn på byggnader, skyddsmurar, allmänna bad, administrativa och kulturella byggnader, en basilika och en stor amfiteater kallad Bouleutherion. När kejsare Diocletianus delade provinsen Dakien i Dacia Ripensis (på Donaus banker) och Dacia Mediterranea, blev Serdica huvudstad i Dacia Mediterranea. Staden utvecklades under ett och ett halvt sekel, vilket gjorde att Konstantin den store kallade den "Mitt Rom".

Serdica var av medelstorlek med ståtligheten hos ett storstadskoncept med planering och arkitektur, med rik munterhet och aktivt socialt liv. Den blomstrade under ledning av den bysantinske kejsaren Justinianus I, då den omringades av stora slottsmurar, vilkas delar man kan se än idag. Staden förstördes av hunner år 447 men återuppbyggdes av Justinianus under namnet Triaditsa.

Sofia blev först en del av Första bulgariska imperiet under regeringen av Krum år 809. Efteråt blev den känd under det slaviska namnet Sredets och växte till ett viktigt slott och administrativt centrum. Efter ett antal misslyckade slag föll staden under det bysantinska riket år 1018, men återigen blev del av det andra bulgariska imperiet under tiden av tsar Ivan Asen I. Från 1100- till 1300-talet var Sofia en viktig plats för handel och hantverk. Den namngavs till Sofia (grekiska för visdom) år 1376 efter kyrkan St. Sofia. Staden kallades både Sofia och Sredets fram till 1500-talet, då det nya namnet gradvis ersatte det gamla.

Sofia togs över av osmanska riket under ledning av Murad I år 1382, och blev huvudstad i den osmanska provinsen (beylerbeylik) Rumelien, som existerade till 1715 då flest katoliker emigrerat.

Under rysk-turkiska kriget (1877-1878) togs Sofia över av ryska trupper och blev år 1879 huvudstad i det autonoma furstendömet Bulgarien, vilket 1908 blev kungadömet Bulgarien. Under andra världskriget bombades Sofia av allierade luftstyrkor under sena 1943 och tidiga 1944, och ockuperades senare av Sovjetunionen. Bulgariens regim, som allierade landet med Nazityskland, besegrades och Sofia blev huvudstad i det kommuniststyrda Folkrepubliken Bulgarien (1944-1989).