Fukushima was born to a samurai family; his father was a retainer to the daimyō of Matsumoto, in Shinano Province (modern Nagano Prefecture).

His quick mind and ability to get along well with people earned him a posting at the Imperial Japanese Army General Staff at an early age.

Fukushima made a reputation during his stay in Berlin, for winning all manner of wagers involving feats of arms or physical strength.

In any case, Fukushima was an admirer of Colonel Burnaby, a British cavalry officer, who had made an epic ride to Khiva in 1874 after receiving word that the Russians had closed the border to Turkistan.

After his return to Japan from his ride across Asia, Fukushima donated his horses to Ueno Zoo in Tokyo, where they quickly became famous tourist attractions.

As a General Staff officer after the war, he visited Egypt, Ottoman Turkey, Persia, Arabia, India, Burma, Siam and Turkistan.

In 1902, he represented Emperor Meiji at the coronation of King Edward VII of Great Britain, and participated in secret diplomatic negotiations behind the Anglo-Japanese Alliance.

Fukushima even composed a poem titled "From Fallen Petal to Rising Star", in which he honored a prostitute who became a patriot through her intelligence-gathering activities.