Liverpools f.d. anfallare sköt in värdarna i ledningen innan Ricardo Pereira fördubblade ledningen.
Marvinhos drog en tillbaka men Thiago Motta avfärdades för sammandrabbning med Paul Baysse innan Anastasios Donis gjorde det 3-1.
Angel Di Maria visades en rak röd för en utmaning på Arnaud Souquet.
Seger för Nice ser dem flytta tre poäng bakom andra plats PSG, som hade vunnit sina tidigare åtta ligamatcher för att hålla sin titel chanser vid liv.
Men Leonardo Jardim Monaco, som har ett spel i hand över PSG, kräver sju poäng från sina senaste fyra matcher att krönas mästare i Frankrike för första gången sedan 2000.
Florian Thauvin gjorde en hatt-trick som Marseille vann 5-1 bort på Caen för att hålla liv i sina förhoppningar om att spela i nästa säsongs Europa League.
Den franska framåt, som är på lån från Newcastle United, gjorde i den andra, 63: e och 89: e minuten mot de nedlåtande-hotade värdar.
Den 24-årige har gjort 15 mål i 35 Ligue 1 matcher sedan flytta till Frankrike i augusti förra året.
Marseille är sjätte i Ligue 1, en punkt bakom femte plats Bordeaux med tre matcher kvar.
En femteplats kommer att säkra en plats i Europa Leagues tredje kvalomgång.
Matchen slutar, Nice 3, Paris Saint Germain 1.
Andra halvlek, Nice 3, Paris Saint Germain 1.
Ángel Di María (Paris Saint Germain) visas det röda kortet.
Foul av Ángel Di María (Paris Saint Germain).
Arnaud Souquet (Nice) vinner en frispark i den defensiva halvan.
Mål!  Nice 3, Paris Saint Germain 1. Anastasios Donis (Nice) rubrik från mycket nära till nedre vänstra hörnet.
Thiago Motta (Paris Saint Germain) visas det röda kortet för våldsamt beteende.
Foul av Thiago Motta (Paris Saint Germain).
Paul Baysse (Nice) vinner en frispark i defensiva halvan.
Marco Verratti (Paris Saint Germain) vinner en frispark i anfallshalvan.
Foul av Mickael Le Bihan (Nice).
Thiago Silva (Paris Saint Germain) vinner en frispark i den defensiva halvan.
Foul av Ricardo Pereira (Nice).
Foul av Thomas Meunier (Paris Saint Germain).
Mickael Le Bihan (Nice) vinner en frispark i defensiva halvan.
Försök missade. Lucas Moura (Paris Saint Germain) höger fotade skott från höger sida av lådan missar till vänster. Hjälpt av Ángel Di María med ett kors.
Ersättare, snygging. Mounir Obbadi ersätter Vincent Koziello.
Försök missade. Thomas Meunier (Paris Saint Germain) höger fotade skott utanför lådan är hög och bred till höger.
Foul av Thomas Meunier (Paris Saint Germain).
Jean Michael Seri (Nice) vinner en frispark i defensiva halvan.
Offside, Paris Saint Germain. Thomas Meunier försöker en genom boll, men Marquinhos fångas offside.
Hörnet, Paris Saint Germain. Förföljd av Arnaud Souquet.
Blaise Matuidi (Paris Saint Germain) vinner en frispark i defensiva halvan.
Foul av Ricardo Pereira (Nice).
Substitution, Paris Saint Germain. Lucas Moura ersätter Julian Draxler.
Ersättare, snygging. Mickael Le Bihan ersätter Mario Balotelli.
Foul av Edinson Cavani (Paris Saint Germain).
Paul Baysse (Nice) vinner en frispark i defensiva halvan.
Försök missade. Ángel Di María (Paris Saint Germain) vänster fotade skott utanför lådan är nära, men missar till höger efter ett hörn.
Försök blockerat. Tiago Motta (Paris Saint Germain) vänster fotade skott från mitten av lådan är blockerad.
Försöket räddades. Tiago Silva (Paris Saint Germain) huvud från mitten av rutan sparas i mitten av målet. Hjälpt av Julian Draxler med ett kors.
Ersättare, snygging. Anastasios Donis ersätter Valentin Eysseric på grund av en skada.
Hörnet, Paris Saint Germain. Sammankallad av Dalbert.
Försök missade. Edinson Cavani (Paris Saint Germain) huvudet från mitten av lådan är hög och bred till vänster. Hjälpt av Ángel Di María med ett kors.
Försöket räddades. Thomas Meunier (Paris Saint Germain) vänster fotade skott från utsidan boxen sparas i mitten av målet.
Hörnet, Paris Saint Germain. Förföljd av Arnaud Souquet.
Marquinhos (Paris Saint Germain) vinner en frispark i defensiva halvan.
Foul av Mario Balotelli (Snyggt).
Foul av Blaise Matuidi (Paris Saint Germain).
Arnaud Souquet (Nice) vinner en frispark i den defensiva halvan.
Mario Balotelli gjorde som Nice slog nio-man Paris St-Germain att lämna Monaco fast i förarsätet för sin första Ligue 1 titel i 17 år.