A origem do lundum está na África Ocidental de onde veio, primeiro para Cabo Verde, depois para Portugal, através dos escravos no século XV e posteriormente no século XVI, épocas em que o batuque se dançava nas ruas de Lisboa. No tempo de D. Manuel I dançava-se o lundum, o batuque e a charamba, que foram proibidos por ordenação régia por serem danças imorais. No século XVII surge no Brasil, na cidade de S. Salvador da Baía, levado pelos escravos da Guiné e da Costa da Mina, mas também de Angola, tendo sido trazido pelos marinheiros para Portugal, onde se tornou muito popular no século XVIII.
Os termos utilizados com referência à dança do lundum eram "bater" ou "riscar" o lundum, com movimentos sensuais de aproximação do ventre, a umbigada. Existe uma possibilidade de que as primeiras versões do fado que eram dançadas tenham a sua origem no lundum. A metrópole teve sempre uma grande preferência pelas danças africanas que foi assimilando como suas e que se tornaram imensamente populares. Algumas destas danças de origem africana tinham nomes curiosos, como canário, guinéu ou charamba, a fofa, o sarambeque, para além de lundum e fado. A chegança foi uma dança que tanto D. João V como D. José proibiram com pena de prisão. Neste contexto, a influência da música africana em Portugal foi sentida muito antes de o jazz surgir na América e estas danças conquistaram primeiro as classes populares antes de passarem pela burguesia e serem definitivamente aceites no seio da aristocracia, apesar de todos acharem se tratar de danças indecorosas.
O escritor Nicolau Tolentino referiu-se na sua obra ao "doce lundum chorado" confirmando-lhe o pendor nostálgico que o fado também viria a ter. O poeta brasileiro Caldas Barbosa viria a causar sensação na sociedade lisboeta do século XVIII pela interpretação na guitarra e na voz de lunduns e modinhas da sua própria autoria. Terá sido talvez através de Caldas Barbosa que o lundum se tornou num ritmo mais vagaroso, arrastado, nostálgico e sentimental que o fado viria a ter na sua versão urbana do século XIX, sendo menos coreográfico e sensual. O lundum que era assim harmonicamente muito semelhante ao fado inicial subiu aos palcos dos teatros, nomeadamente do S. Carlos. O lundum foi ainda influenciar outras danças sul-americanas, como a zamacueca ou samba-cueca no Peru, na Argentina e no Chile.