It is originally from the southern coastal regions of Iran, but has become a popular food item among Arab states of the Persian Gulf, brought by the migration of the Persian Huwala and Ajam communities to the region. It is typically served on top of khubz (Arabic flatbread), and Regag & Falazi a wafer thin crispy flat bread that resembles crepe. Mahyawa is made from salted Anchovies and ingredients include: fennel seeds, cumin seeds, coriander seeds and mustard seeds.
It is usually sold at Iranian bread stores, in distinctive clear bottles, showing the brown colored sauce.
According to folk stories; in the early 1800s there was a leprosy epidemic in southern Iran. A Greek doctor traveling through the gulf prescribed mustard as treatment. However, mustard didn't fit the culinary styles of the area. So they experimented with different recipes using mustard and came up with Mahyawa.