The Japanese Milichiidae are taxonomically revised with four newly recorded genera (Milichia, Madiza, Neophyllomyza, and Leptometopa). Two new species of Milichia and Neophyllomyza are described: Milichia yafusoae sp. nov. was discovered on guano of the Southeast Asian long-fingered bat (Mineopterus fuscus Bonhote) in a limestone cave of Okinawa Island, Ryukyu Archipelago; Neophyllomyza nishidai sp. nov. was collected from flowers of Aristolochia debilis Siebold et Zucc. (Aristolochiacea) which have trap-and-release mechanisms for using flies as pollinators in Honshu. Two species, Leptometopa latipes (Meigen) and Madiza glabra (Fallén), are recorded from Japan for the first time. Bionomic remarks for each species and a key to the genera and species of the Japanese Milichiidae are also provided.