W 1939 roku, w przededniu II wojny światowej, został powołany na adiutanta admirała Johna Godfreya, szefa British Department of Naval Intelligence. W służbie tej zasłynął jako twórca idei operacji Ruthless, nigdy ostatecznie nie zrealizowanej, której zadaniem było zdobycie Enigmy stosowanej przez Kriegsmarine. Na kartach sensacyjnej książki autorstwa Anthony Mastersa (The Man Who Was M: The Life of Charles Henry Maxwell Knight) Fleming występuje też jako główny organizator akcji wylotu Rudolfa Heßa z Niemiec (w 1941 roku) – jego rzekomy udział w tej akcji jest jednak prawdopodobnie tylko fikcją literacką.
Osobiste doświadczenia z pracy w wywiadzie wojskowym stały się kanwą wielu powieści szpiegowskich pisanych przez Fleminga. Pierwsza powieść z udziałem Jamesa Bonda, Casino Royale, została wydana w 1953 roku. Uważa się dość powszechnie, że główna postać kobieca z Casino Royale była zainspirowana przez agentkę Krystynę Skarbek, pracującą dla SOE. Informacja ta została podana przez brytyjskiego dziennikarza Donalda McCormicka. Podobnie twierdził William F. Nolan.