Allerede etter sju minutter styrte Thiago Silva inn en corner med det venstre kneet da Neymar nøyde seg med assistentrollen.
Midtveis i andre omgang viste den andre midtstopperen, David Luiz, at også han kan mer enn å forsvare seg.
VG LIVE: Vi fulgte kampen direkte her!
Fra rundt 25 meter banket han ballen i keeperhjørnet med sin spesielle frisparkteknikk og feiret ellevilt. Luiz, som skal spille sammen med nettopp Silva i PSG kommende sesong, løp ned til det ene hjørneflagget og sparket det overende før han pekte mot himmelen.
VM-kometen James Rodriguez reduserte fra straffemerket med sin sjette scoring i mesterskapet ti minutter før slutt, men de nevnte midtstopperne holdt unna da Colombia trykket de siste minuttene.
To minutter før slutt holdt hele Estadio Castelao pusten da Neymar gikk i bakken etter å ha fått et kne i ryggen i en duell og ble båret gråtende av banen.
Brasil (4-2-3-1): Julio Cesar 5 – Maicon 7, Thiago Silva 8, David Luiz 7, Marcelo 6 – Fernandinho 7, Paulinho 6 (Hernanes fra 86.) – Hulk 7 (Ramires fra 83.), Oscar 5, Neymar 6 (Henrique fra 88.) – Fred 5.
Colombia (4-4-2): David Ospina 5 - Juan Zuniga 5, Christian Zapata 5, Mario Yepes 6, Pablo Armero 5 - Juan Cuadrado 6 (Juan Quintero fra 80.), Freddy Guarin 6, Carlos Sanchez 4, Victor Ibarbo 4 (Adrian Ramos fra 45. 4) - Teofilo Gutierrez 4 (Carlos Bacca fra 70.), James Rodriguez 5.
Sjanser: 5-2
Dommer: Carlos Velasco Carballo (Spania) 5
Dypt inne i overtiden sendte Colombia også keeper David Ospina frem på et frispark, men en nikk endte langt over mål og de mildt sagt entusiastiske tilskuerne slapp jubelen løs vel vitende om vertsnasjonen skal spille semifinale mot Tyskland - en reprise på finalen fra 2002.
- Vi sluttet aldri med å drømme at vi kunne vinne denne kampen. Vi har ventet lenge på å kunne være med i VM igjen, og vi har vist frem noen svært talentfulle spillere, sier Colombia-sjef José Pekerman.
Et skår i gleden for landslagssjef Luiz Felipe Scolari er at kaptein Thiago Silva mister gigantduellen neste uke. Midtstopperen pådro seg et unødvendig gult kort da han løp inn i keeper Ospina da han skulle skyte ut etter pause og må sone mot tyskerne.
- Jeg forstår ikke det gule kortet. Det blir vanskelig mot Tyskland, men vi har gode erstattere, sier Brasils Luiz Felipe Scolari.
Suspenderte Silva har blitt kritisert i Brasil for å vise for mye følelser. I et intervju vist på TV 2 etter kampslutt forklarte han tårene.
- Det er mye følelser i sving. Dette er noe jeg har tenkt over. Jeg har sett på andre utøvere i andre idretter. De ofrer kropp og sjel. Det er nok derfor tårene kommer. Det er det samme for meg. Følelsene tar overhånd siden jeg legger ned kropp og sjel i dette laget.
- Det som er sagt om gråt, er overdrevet, skyter landslagssjef Scolari inn.
Det kokte på tribunene i Fortaleza etter det tidlig ledermålet, men kun fire minutter rystet Colombia vertene da Juan Cuadrado skjøt like utenfor via Silvas fot.
James Rodriguez var ikke like sentral som tidligere i mesterskapet i kvartfinalen og bidro blant annet til å rote bort det som kunne blitt en stor sjanse da Colombia kom fire mot to på en overgang før pause.
Hulk fikk to gode muligheter til å øke ledelsen, men ved begge anledninger var Ospina raskt nede og reddet.
Colombia yppet seg og fikk et «mål» korrekt annullert for offside i minuttene før Luiz banket inn 2-0-målet fra langt hold.
Kampen virket avgjort, men colombianernes håp ble tent da innbytter Carlos Bacca ble lagt i bakken etter å ha vippet ballen forbi keeper Julio Cesar. Rodriguez beholdt roen og trillet inn sin sjette VM-scoring og det som skulle vise seg å bli et trøstemål fra krittmerket.
- Jobben han har gjort, har vært enestående. Vi har ventet litt på det, han er en strålende spiller med stort talent og ambisjoner. Han prøvde å gjøre sitt beste mot en vanskelig motstander, men VM har mistet en av sine beste spillere, sier Pekerman om Colombias store stjerne - som ender på seks mål og to målgivende på fem kamper - pluss at han har vært sterkt involvert i totalt 11 av Colombias 12 mål.
James Rodríguez ble trøstet av Brasils matchvinner David Luiz etter kampen og forlot stadion gråtende. Mens Luiz ruslet rundt med Colombias trøye nummer 10 og minnet egentlig kraftig om Carlos Valderrama der han gikk og vinket til ekstatiske, men lettede supportere på Estádio Castelão.
Luiz Felipe Scolari bidro sterkt i jubelscenene etter kampslutt og kan nå gjøre seg klar for sin tredje VM-semifinale på tre forsøk.
- Det som avgjør i VM, er når du er tøff. Brasil har blitt kritisert tidligere med Dunga som sjef. Men det forsvaret de har nå vil vinne dem mesterskapet, sier Viasat-ekspert Jan Åge Fjørtoft i VGTVs VM-studio.
Den spanske dommeren Carlos Velasco Carballo fikk fullstendig slakt av VGTVs studiogjester, spesielt etter en situasjon der Brasils Neymar fikk stå altfor nærme i en frisparksituasjon.
Viasats ekspert Jan Åge Fjørtoft er full av lovord om Brasils store stjerne Neymar, som fredag møter James Rodriguez og Colombia i kvartfinalen.
VGTVs VM-studio er godt plassert på VG-huset i Oslo, men samarbeid med utplasserte journalister i Brasil gir rykende fersk stemningsrapporter fra folkefesten Sør-Amerika. VGs Øyvind Herrebrøden var ute i gatene før Brasil møter Colombia i kveld, og han mener at det er to av verdens beste supportergrupperinger som samles i kveld.