A new Myxozoa, Kudoa quraishii n. sp., is reported in the striated muscle of the Indian mackerel Rastrelliger kanagurta from the Red Sea and the Arabian Gulf in Saudi Arabia. Mean prevalence of infection is about 20 % and varies between localities. The parasite develops whitish and oval or rounded pseudocysts of 0.2–3 mm in the striated muscles of the body. Pseudocysts are filled with mature spores. Myxospores are quadrate in shape in apical view with rounded edges and ovoid in side view. Each spore is formed by four equal shell valves and four symmetrical polar capsules. Polar capsules are pyriform in apical view and drop-like in side view. Myxospore measurements in micrometers are 6.14 (5.9–6.34) in width, 5.48 (5.3–5.71) in thickness, and 4.27 (4.1–4.42) in length. Polar capsule measurements in apical view in micrometers are 2.08 (1.88–2.28) and 1.31 (1.10–1.52) length by width. Molecular analysis based on SSU rDNA gene shows closest association with K. amamiensis and K. kenti with respectively 98 and 97.2 % of similarities.