Det amerikanska nätverket hävdade att det fanns "no-go områden" i den franska huvudstaden där polis och icke-muslimer vägrade att gå.
Anne Hidalgo sa att folket i Paris hade blivit "förolämpat" och stadens bild hade blivit "skadad".
Nätverket har sedan dess bett om ursäkt för att ha gjort "regrettable fel" i luften om den muslimska befolkningen.
Ms Hidalgo sa till CNN: "När vi blir förolämpade och när vi har fått en image, då tror jag att vi måste stämma. Jag tror att vi måste gå till domstol, för att få dessa ord borttagna.
"Paris image är fördomsfull och Paris ära fördomsfull."
Hennes ord upprepades av vice borgmästaren, Patrick Klugman.
I en intervju med BBC sa han att Ms Hidalgo var "definitivt seriös" om sin avsikt att stämma Fox News.
"Vi har våra juridiska rådgivare som arbetar med fallet", tillade han. "Vi undersöker under vilken jurisdiktion fallet ska tas upp, Paris eller New York."
Som svar till Anna Hidalgo sade Fox News verkställande vice ordförande Michael Clemente: "Vi hyser medkänsla med Frankrikes medborgare när de går igenom en läkningsprocess och återvänder till vardagen.
"Vi finner dock borgmästarens kommentarer om en stämning missriktad."
Fox har också bett om ursäkt för kommentarer av terrorexperten Steven Emerson, som hävdade att Birmingham var "helt Muselman" och styrd av Sharia lag.
Fox News värd Jeanine Pirro senare sade Emerson hade "gjort ett allvarligt sakfel som vi felaktigt lät stå obestridd och okorrigerad".
Emerson sade att han gjort ett "oförlåtligt misstag".
Premiärminister David Cameron svarade med att kalla honom "en komplett idiot".
I en annan ursäkt under helgen, Fox News presenter Julie Banderas sade kanalen hade "gjort några beklagliga misstag i luften om den muslimska befolkningen i Europa", och bad "till alla som kan ha tagit anstöt, inklusive folket i Frankrike och England".
Paris borgmästare har sagt att hon kommer att stämma Fox News för dess felaktiga rapportering om staden efter attacken på tidningen Charlie Hebdo.