Jon McLaughlin gjorde flera smarta stopp innan Chris O'Grady knackade in mot sin gamla klubb för att sätta Brewers framåt.
Millers hade varit på toppen men föll längre efter när John Brayford korsade för Jackson Irvine att gå in.
Tom Adeyemi reagerade snabbast på en räddning för att dra en tillbaka, men Rotherham saknade kvaliteten för att hitta en equalizer.
Återupplev Burtons seger i Rotherham som hände
Besegra lämnar Yorkshire sida, ledd av vaktmästare Paul Warne, 10 poäng från säkerhet, medan Burton flytta upp två platser till 19: e.
Det var en första bort triumf för säsongen för Nigel Clough sida medan O'Grady mål var hans första i 389 dagar, som han var på handen för att göra mål efter Lewis Price spillde ett skott.
Burton full-back Brayford tillbringade flera minuter att behandlas efter en huvudskada, men kom tillbaka för att hjälpa Irvine innan ersättas i intervallet.
Rotherham jagade back-to-back Championship segrar för första gången denna säsong, men de har nu medgett 52 liga mål.
Darnell Fisher volleyed bred och Izzy Brown kunde inte hitta målet inifrån området som värdarna pressade, förgäves, för en punkt.
Burton manager Nigel Clough: "Vi spelade inte i närheten av lika bra som vi gjorde på Aston Villa på Boxing Day, men vi kämpade bort för tre poäng.
"Det var tufft att komma hit, vi visste att de skulle ha sina svansar upp. Vi visste att de skulle komma ut och orsaka oss problem, och det gjorde de.
"Den enda besvikelsen var att vi medgav strax före halvtid och det gav dem en chans, de satte oss under stor press i den andra halvan.
"Timeningen på året ville vi inte gå in i det nya året utan en bort vinst. Det är viktigt psykologiskt att inte vara i botten tre på väg in i det nya året."
Rotherhams vaktmästare Paul Warne: " Vi spelade riktigt bra. Vi var ett bättre team och när det gäller Burton trodde jag att de kom för en poäng.
"Jag älskar mina pojkar men med största respekt för dem, de är inte vana att spela mot och behöva bryta ner två banker av fyra.
"Gjorde de sig underlägsna i mållinjen? Ja, det är det. Men var de underlägsna i föreställningen? Nej, det tror jag inte.
"De är förkrossade, det kommer att bli svårt att plocka upp dem. Men jag tror inte att vi är förvisade, jag tror fortfarande att vi har en chans.
"Om jag inte gjorde det skulle jag be ordföranden att ta in en annan vaktmästare."
Matchändar, Rotherham United 1, Burton Albion 2.
Darnell Fisher (Rotherham United) visas det gula kortet.
Andra halvlek, Rotherham United 1, Burton Albion 2.
Hörnet, Rotherham United. Förföljd av Tom Flanagan.
Foul av Jesaja Brown (Rotherham United).
Lucas Akins (Burton Albion) vinner en frispark i den defensiva halvan.
Shaun Barker (Burton Albion) visas det gula kortet för en dålig foul.
Lee Frecklington (Rotherham United) vinner en frispark på vänsterflygeln.
Foul av Shaun Barker (Burton Albion).
Substitution, Burton Albion. Shaun Barker ersätter Matthew Palmer.
Försening över. De är redo att fortsätta.
Försening i match Lucas Akins (Burton Albion) på grund av en skada.
Foul av Peter Odemwingie (Rotherham United).
Lucas Akins (Burton Albion) vinner en frispark i den defensiva halvan.
Danny Ward (Rotherham United) visas det gula kortet för en dålig foul.
Hörnet, Rotherham United. Förföljd av Tom Flanagan.
Försöket räddades. Peter Odemwingie (Rotherham United) höger fotade skott från utsidan rutan sparas i nedre högra hörnet.
Substitution, Rotherham United. Dexter Blackstock ersätter Joe Mattock.
Darnell Fisher (Rotherham United) vinner en frispark i anfallshalvan.
Foul av Tom Naylor (Burton Albion).
Utombords, Burton Albion. Lloyd Dyer försöker en genom boll, men Lucas Akins fångas offside.
Foul av Aimen Belajed (Rotherham United).
Marcus Myers-Harness (Burton Albion) vinner en frispark på högerkanten.
Försök missade. Lee Frecklington (Rotherham United) höger fotade skott från utsidan av lådan missar till vänster.
Substitution, Rotherham United. Greg Halford ersätter Tom Adeyemi.
Försök missade. Jesaja Brown (Rotherham United) höger fotade skott från vänster sida av lådan missar till höger. Hjälpt av Peter Odemwingie.
Hörnet, Rotherham United. Förföljd av Damien McCrory.
Damien McCrory (Burton Albion) visas det gula kortet för en dålig foul.
Peter Odemwingie (Rotherham United) vinner en frispark på högerkanten.
Foul av Damien McCrory (Burton Albion).
Joe Newell (Rotherham United) vinner en frispark i den defensiva halvan.
Foul av Lucas Akins (Burton Albion).
Försöket räddades. Peter Odemwingie (Rotherham United) vänster fotade skott från utsidan boxen sparas i mitten av målet. Hjälpt av Lee Frecklington.
Matthew Palmer (Burton Albion) visas det gula kortet.
Foul av Lee Frecklington (Rotherham United).
Lucas Akins (Burton Albion) vinner en frispark i anfallshalvan.
Hörnet, Burton Albion. Förföljd av Joe Mattock.
Offside, Rotherham United. Aimen Belaped försöker en genom boll, men Peter Odemwingie fångas offside.
Substitution, Burton Albion. Marcus Myers-Harness ersätter Chris O'Grady.
Försök missade. Darnell Fisher (Rotherham United) höger fotade skott från höger sida av lådan är hög och bred till höger.
Två snabba första-halva mål hjälpte Burton kanten förbi botten sidan Rotherham och flytta fem poäng bort från Championship relegationszonen.