Den statliga oljebyråns tekniker upptäckte en av världens största oljereserver djupt under havsbottnen - under miltals saltlager.
Två år senare slog den till guld igen och hittade ännu ett jättelikt oljereservat.
Optimismen var hög. Företaget gick till marknaderna och samlade in över 70 miljarder dollar - världens största aktieemission någonsin.
Brasiliens ekonomi var också i marschfart, och till slut tog den fart efter många år av mager tillväxt.
Men de goda tiderna varade inte länge - varken för företaget eller landet. En omfattande korruptionsskandal förra året urholkade mycket av Petrobras marknadsvärde.
Brasiliens ekonomi har också varit i en nedåtgående spiral - med hög inflation, långsam tillväxt och lågt förtroende.
Så hur gick det så fel, så fort?
Petrobras oljebonanza och Brasiliens framväxande stjärnstatus är ganska nya fenomen.
För bara några årtionden sedan var utsikterna ödesdigra för båda.
I början av 1990-talet var Brasilien en ung demokrati i djupa ekonomiska svårigheter.
Den årliga inflationen var nära 5000 %. Årtionden av protektionism innebar att konkurrensen var liten inom de flesta sektorer och att många nationella företag hade blivit ineffektiva.
Petrobras sågs som en del av det landskapet av många som ville privatisera det.
En kritiker brukade kalla det "Petrossauro" - en stor, föråldrad struktur som rörde sig långsamt och var dömd till utrotning i den moderna världen.
Brasiliens förmögenheter började förändras i mitten av 1990-talet - både internt och externt.
Genom reformer kunde på varandra följande regeringar besegra hyperinflationen, öppna Brasiliens ekonomi för världen och omfördela tillväxten och lyfta miljoner ur fattigdomen.
Ett decennium av global ekonomisk högkonjunktur gynnade Brasiliens förkämpe för export - varor som kaffe, soja, nötkött och olja.
Brasiliens oljesektor öppnades för utländska företag, men lokala lagar såg till att Petrobras höll sin roll i toppen av varje större projekt.
Ett decennium av höga internationella oljepriser bidrog till att ge ett stort uppsving åt företagets investeringsplaner.
År 2010 - efter alla oljefyndigheter - kändes det som om Brasilien och Petrobras äntligen hade "ankommit" på toppen.
Men sen tog det en vändning till det sämre.
Ett problem var Petrobras desperata behov av pengar.
Brasiliens skattkammare ligger djupt under saltlagret och kan bara utvinnas med dyra metoder.
President Dilma Rousseff var övertygad om att Petrobras skulle spela en viktig roll på alla områden, även om han inte hade resurser att göra det ensam.
Så företaget försökte locka partners och samla in pengar utomlands genom att sälja många av sina tillgångar.
På samma sätt som Petrobras stod inför sin största ekonomiska utmaning någonsin drabbades han av ett återkommande hinder i Brasiliens historia: korruption.
En undersökning av Brasiliens federala polis visade att den statliga oljejätten användes illegalt som en kontantko för de flesta parter i regeringskoalitionen.
Dess högsta chefer är alla politiskt utnämnda av regeringen.
De delade ut Petrobras kontrakt i utbyte mot partidonationer och mutor.
En rad uppmärksammade gripanden gjordes - från de bästa brasilianska VD:arna till kassören av Rousseffs styrande parti.
Mer än 40 nyckelpolitiker är under utredning, bland annat ordförandena för kongressens båda hus.
Förtroendet för företaget urholkades nästan över en natt - både på marknaderna och på gatorna.
Dess egen VD fick sparken för att inte kunna hantera krisen.
Tiotusentals brasilianare gick ut på gatorna mot president Rousseff - som var ordförande för Petrobras styrelse under en stor del av den period då de påstådda mutorna inträffade.
Det kunde inte ha kommit vid en sämre tidpunkt för Brasiliens ekonomi.
Den är fast i låg växel, nu när varuboomen verkar vara över, och dess varor är inte längre i hög efterfrågan.
Fram till förra året hade regeringen försökt ta sig igenom krisen genom att öka utgifterna och pumpa in pengar i ekonomin.
Det försaltade skiktet består av sten som lades ner för miljontals år sedan innan ett saltlager - som kan vara tusentals meter tjockt - ansamlades ovanför det.
En del av den olja som bildas i saltlagret har inte läckt upp i lagren ovan.
Denna olja är ofta av god kvalitet, men är begravd så djupt att tillgången till den är svår.
Enligt Petrobras kan det finnas 50 miljarder fat olja i det försalta lagret som finns i den brasilianska kontinentalsockeln.
Petrobras själv användes som ett instrument för denna politik.
Det statliga oljebolaget kontrollerar det interna bränslepriset, och under tre år hjälpte det brasilianarna att få billigare bensin.
Men subventionerna skadade företaget vid en tidpunkt då det behövde alla pengar som det kunde få för sitt försalta projekt.
Nu har regeringen gjort en u-sväng i sin politik, går radikalt från stimulans till åtstramningar.
Tidigare har Petrobras hjälpt regeringen att ta sig igenom nedgångar, eftersom enbart dess investeringar står för 2 % av Brasiliens bruttonationalprodukt.
Men nu gör det saken ännu värre.
En undersökning av FGV Business School tyder på att Petrobras investering skulle kunna slå ner omkring 30 miljarder dollar på den brasilianska ekonomin, med mer än en miljon förlorade arbetstillfällen, främst inom byggsektorn.
Petrobras och Brasilien har försökt reagera på krisen med ett tryck på öppenhet.
Senare denna månad kommer den att ersätta vissa politiker i styrelsen med respekterade marknadssiffror, som gruvjätten Vales president Murilo Ferreira.
Energiministern har till och med signalerat att regeringen kan underlätta tillgången till försalta projekt för utländska företag, vilket minskar bördan för Petrobras.
En del säger att Brasilien har lärt sig en del saker.
"Om man koncentrerar allt - all rikedom - i ett enda företag som kontrolleras av staten är det mycket lätt för det politiska systemet att gå dit och försöka ta resurser", säger Sergio Lazzarini, akademiker vid Insper Business School.
"Du kan undvika detta med mer konkurrens, mer öppenhet, mer reglering."
Brasilien och Petrobras har fortfarande en svår väg att följa.
De flesta ekonomer förutspår att Brasilien kommer att vara i recession i år.
Och korruptionsskandalen är långt ifrån över, eftersom ingen har prövats ännu.
President Rousseff insisterar på att Brasilien och Petrobras kommer att bli starkare efter denna kris, eftersom den historiska korruptionen äntligen undersöks efter årtionden av försummelse.
Brasilianarna hoppas att hon har rätt, men stämningen i landet är dyster.
Efter årtionden av låga förväntningar hade brasilianarna under de senaste åren kommit att tänka att nationen till slut var på väg in i världsscenen som en global makt, bara för att se den återigen fastna i korruption och låg tillväxt.
Även om många fortfarande erkänner att landet har det mycket bättre än under åren av hyperinflation och "Petrossauro", har optimismen nu i stor utsträckning ersatts av skepticism och otålighet.
Brasiliens skattkammare, verkar det, kommer att ta ett tag längre tid att gräva ut.
År 2008, Petrobras och dess viktigaste intressent - Brasiliens regering - slog jackpotten.