For this album, Bashung worked with the English record producer and engineer Ian Caple and with artists such as the Valentins, Rodolphe Burger, Joseph Racaille and Adrian Utley of Portishead. Most of the songs were written by Jean Fauque.
Fantaisie militaire marked a turn in Bashung's career. He was awarded three Victoires de la musique awards in 1999: Male Artist of the Year, Best Album of the Year, and Video of the Year for the single "La nuit je mens". In 2005, the Victoires ranked it the best French album since 1985. The Belgian rock historian Gilles Verlant included the album in his book La discothèque parfaite de l'odyssée du rock, lauding it as a "chef d'œuvre" and the "shining diamond of the winter of 1998". He added that the album showed "Bashung mix the sounds and his inspiration with a perfect mastery of studio incidents" and that "its precision is that of a goldsmith, a jeweler, a maniac watchmaker". In 2010, the French edition of Rolling Stone magazine named Fantaisie militaire the ninth greatest French rock album ever made.