Efter en dominant start från besökarna exploderade Aberdeen in i livet när Jonny Hayes sköt hem en ostoppbar bil från 25 meter.
Simon Church markerade sin debut med ett mål när han buntade hem från nära håll för att göra det 2-0 på Pittodrie.
Leigh Griffiths drog en tillbaka i skadan tid, men Dons höll på att minska gapet på Celtic till tre punkter.
Det var en sensationell atmosfär i denna top-of-the-table sammandrabbning, som såg strejker Church göra sin debut för värdarna med Efe Ambrose ta en plats på bänken.
De tidiga utbytena var stridande och engagerade men begränsade till långsiktiga insatser som inte hotade en öppnare.
Celtic växte i förtroende framöver under första halvan, och det fanns starka anspråk på ett straff som Shay Logan ansågs ha hanterat bollen.
Tävlingen bröt då ut och det var Aberdeen som slog till beslutsamt.
Hayes samlade en klarering ungefär 25 meter från målet och slog till mot en fantastisk strejk som kröp in i målvakten Craig Gordons post.
Som keltisk chef Ronny Deila såg på i skräck, blev det värre för hans sida när Aberdeen rytade längre fram.
Hayes skickade in ett hörn, Kenny McLean nickade på och debutant Church knänade bollen hem från nära håll för att skicka Pittodrie wild.
McLean kom nära en tredjedel strax före halvtid med en våldsam drive utanför lådan som Gordon avled.
Deilas reaktion på halvtid var att debutera Colin Kazim-Richards på Stuart Armstrongs bekostnad.
Men det var Aberdeen som borde ha gått längre.
Defensiv obeslutsamhet gav kyrkan en härlig chans att försegla den, men på något sätt skruvade han bollen brett från nära håll.
Celtic kämpade för att skapa tills Scott Brown kopplade bollen över för Griffiths, som såg säker på att begrava en rubrik tillbaka över mål, men det inched förbi det avlägsna inlägget.
Niall McGinn sköt sedan på avstånd och Gordon rensade bollen som det såg ut att vara på väg precis bred.
Sedan Griffiths skära in på sin vänstra fot och sköt förbi Scott Brown för att dra en tillbaka för Celtic i stoppage tid, men det fanns inte tillräckligt med tid kvar för att söka efter en equalizer.
Aberdeen andades nytt liv in i Premiership titeln ras med en välförtjänt seger mot ligan ledare Celtic.