A loan translation of French danse du ventre. First attested in English in the 1890s.
OED has as earliest attestation an explicit gloss of 1899, "The danse du ventre (literally, "belly-dance") is of Turkish origin" (in Bohemian Paris of to-day), but there are slightly earlier occurrences, in In the land of the lion and sun; or, Modern Persia (1891) of Persian dance; in Frank Leslie's popular monthly (vol. 36, 1893) "These women dance, not with their feet and arms but with their stomach. Hence their abdominal contortions are styled the 'belly dance.'"; and in Untrodden fields of anthropology (1898) in reference to African (Wolof and Landoma (Baga)) dance.