Vietjet Air announced the Hanoi-Fukuoka service would begin on July 2 with three weekly flights and the Hanoi-Fukuoka service start a day later with four weekly flights.
It is also set to resume the Da Nang-Tokyo service on July 8.
Japan will waive mandatory quarantine for people arriving from Vietnam who have got three Covid-19 vaccine shots starting later this month.
Bamboo Airways began flying from HCMC to Singapore last month with two flights a week, and plans to increase the frequency to three from May 24.
It also plans to double the frequency of its HCMC-Bangkok service to four flights from June 1.
Southeast Asian countries like Thailand, Singapore and Malaysia have lifted Covid restrictions and allow quarantine-free entry for tourists from Vietnam.