Han berättade för BBC att han hade varit i samtal med Labour MPs men tillade: "Vi måste fortsätta att bygga fallet".
Han medgav att det skulle vara svårare att få stöd om Labour beordrade sina parlamentsledamöter att rösta mot flyganfall i Syrien.
Labours Jeremy Corbyn, som motsätter sig flyganfall, sade att han inte hade bestämt sig för att erbjuda dem en fri omröstning.
Parlamentsledamöterna skulle kunna rösta nästa vecka om huruvida Storbritanniens flygstrejker mot IS ska utvidgas till Syrien, men regeringen har sagt att den inte kommer att kalla på omröstningen om den inte är säker på att vinna.
Ministrarna behöver stöd av tillräckligt många parlamentsledamöter från Labour för att kompensera konservativa rebeller som kommer att rösta emot militärt ingripande, och Fallon sade att han hade informerat Labour parlamentsledamöter om regeringens fall.
Allt handlar om siffrorna. Även om regeringen har en majoritet på 12 ledamöter, hyser ett antal konservativa parlamentsledamöter - kanske ett dussin - starka tvivel om att utvidga flyganfallen till Syrien.
Och regeringen kommer inte att riskera ett nederlag i underhuset. I själva verket vill den ha en stark seger.
Regeringen kommer inte att få stöd av SNP MPs, den tredje största parten i parlamentet, så det behöver en del av Labour MPs med det.
Vissa arbetarparlamentsledamöter hade genomgångar med MoD i helgen och brottas med argumenten, lyssnar på väljare.
Det är därför Jeremy Corbyns beslut är så viktigt.
Om han tillåter en fri omröstning, kanske hälften av hans skuggskåp och runt 60 Labour parlamentsledamöter kan rösta för flyganfall. Om han insisterar på kollektiv opposition kommer det att finnas en allsmäktig rad inom det parlamentariska labourpartiet som skulle kunna förstöra regeringens planer.
En skuggminister har sagt mig att det finns en chans att Labour inte kommer att komma överens om en ståndpunkt alls på måndag och kommer att vänta på formuleringen av regeringens förslag innan beslut om hur man ska rösta.
Det kommer att bli en avgörande vecka.
Frågade om siffrorna fanns för att stödja åtgärder sade Fallon "inte ännu", men att ministrarna "arbetade på det".
"Du bör inte förlänga militära operationer lätt", sade han. "Det finns legitima frågor att besvara och vi gör vårt bästa för att svara på dem."
Han avvisade också förslag om att angripa IS, även känd som Isil, skulle göra Förenade kungariket mer till ett mål. säger: "Det finns alltid risker i krig men det finns en större risk att inte göra något åt Isil och lämna våra gator sårbara för den typ av slakt vi såg i Paris."
Parlamentsledamöterna avvisade en röst för flygstrejker mot syriska regeringsmål 2013. Den deltar dock i flygstrejker mot IS i Irak efter att parlamentsledamöter stödde flytten förra året.
Corbyn, som har uttryckt sitt motstånd mot bombningar, upprepade sin ståndpunkt och sade att han "allvarligt ifrågasätter" regeringens påstående att det finns 70.000 måttliga oppositionskämpar på plats.
Han sade: "Det måste också finnas ett erkännande att om vi bombar i Raqqa kommer vi att döda civila liv, vi kanske inte i själva verket gör så mycket skada på Isil och faktiskt kan göra situationen värre inte bättre."
Labourledaren sade att det skulle vara hans sak att besluta om han skulle erbjuda sina parlamentsledamöter en fri röst, vilket skulle innebära att de inte skulle vara tvungna att följa partilinjen.
Han tillade: " Inget beslut har fattats om detta ännu, Jag kommer att ta reda på vad parlamentsledamöter tycker.
"Tydligen finns det starka åsikter om båda riktningarna. Vi kommer att föra ytterligare en diskussion om detta. Vi kommer att fatta det beslutet inte just nu utan senare."
Corbyn sade att han hade fått 70.000 svar på en undersökning som sändes ut till laboursupportrar i fredags genom att gå igenom deras åsikter om flygstrejker, och ett beslut skulle fattas "som parti".
Det ökar trycket för en fri omröstning, ett drag som stöds av skuggkanslern och Corbyn ally John McDonnell.
Shadow Justice Secretary Lord Falconer sade att det fanns "betydande skillnader" inom Corbyns toppgrupp i den fråga som han inte trodde kunde förenas med.
Tidigare skuggföredragande Chuka Umunna sade att han skulle rösta med sitt samvete även om han beordrades att följa partilinjen och tillade på Sky News att det inte var någon skam att det fanns ett brett spektrum av åsikter i frågor om krig och fred inom Labours led.
Både Unnna och Lord Falconer sade att de var beredda att stödja flyganfall.
Arbetstagarledamoten Stephen Kinnock, som planerar att motsätta sig flyganfall, sade att en fri röst borde erbjudas eftersom frågan är en " samvetsfråga".
Men två andra parlamentsledamöter, som båda föreslog att de också skulle rösta mot flyganfall, sade att de ansåg att omröstningen borde piskas.
På BBC Radio 4s The World This Weekend kritiserade både Liam Byrne och Jess Phillips Corbyns hantering av situationen.
SNP vice ledare Stewart Hosie sade sitt parti hade inte övertygats av argumentet för militära åtgärder.
Om inte regeringen kunde lägga fram en plan "för att undvika anarki i Libyen", sade han, "visst skulle vi inte kunna stödja konflikter i det nuvarande klimatet".
UKIP:s Nigel Farage avfärdade regeringens strategi.
"Vad premiärministern och Michael Fallon sa är, låt oss skicka ytterligare tre jetplan, det är allt vi pratar om. Jag är ledsen, jag tror inte på det. Jag har hört dessa argument om upprepade militära ingripanden."
Regeringen har ännu inte tillräckligt med röster från parlamentsledamöter för att backa luftangrepp mot Islamiska staten (IS) i Syrien, Försvarsminister Michael Fallon sade.