Polkka on peräisin itäisestä Böömistä nykyisen Tshekin alueelta. Böömiläiset historioitsijat arvelevat, että tanssin keksi talonpoikaistyttö Anna Slezak Labska Tynicessä eräänä sunnuntaipäivänä vuonna 1834. Tanssi sovitettiin kansanlauluun "Strycek Nimra Koupil Simla" (Nimra-setä toi valkoisen hevosen). Anna käytti askelikosta nimeä madera. Kertomuksen todenperäisyydestä ei ole varmuutta.
Vuonna 1835 tanssi esiteltiin prahalaisessa tanssisalissa nimellä pulka, joka tarkoittaa lyhyttä askelta. Vuonna 1840 prahalainen tanssinopettaja Raab tanssi polkkaa Odéon-teatterissa Pariisissa. Menestys oli valtaisa. Seuraavan kymmenen vuoden aikana tanssi levisi ympäri Euroopan ja myös Amerikan mantereelle.
Kirjallisuudesta on vaikea löytää tietoa siitä, miten alkuperäistä böömiläistä polkkaa tanssittiin, mutta The Illustrated London News julkaisi seuraavan ohjeen 11. toukokuuta 1844. Polkka oli tällöin uutuus Englannissa. Tahti lasketaan 1-2-3-4, ja ohjeen mukaan silloinen askelikko tanssittiin näin:
Sen jälkeen seuraa sama askelikko alkaen hypyllä vasemmalla jalalla.
Artikkelin mukaan tämä oli "Drawing-room Polka, as danced at Almack's and at the balls of the nobility and gentry of this country". Artikkelissa annetaan ymmärtää, että böömiläisten talonpoikien polkka oli jotain vähemmän sivistynyttä. Koska juuri "nobility and gentry" oli se ryhmä, joka matkusteli ja levitti tanssia, vaikuttaa todennäköiseltä, että tämä tyyli on ollut myöhempien yleiseurooppalaisten ja kansallisten tyylien lähtökohtana.
Suomeen polkkaa tuli tiettävästi ensiksi ruotsinkieliselle alueelle vuonna 1843. Helsinkiin sen kerrotaan saapuneen kesällä 1844. Aluksi vain muuutama uskalias pari yritteli sitä Helsingin Kaivohuoneella, mutta puoli vuotta myöhemmin kaikki kynnelle kykenevät olivat sen valloissa. Tanssi levisi nopeasti myös kansan keskuuteen ja saavutti maaseudulla suuren suosion.
Mikään muu kansa ei ole tanssinut polkkaa niin paljon kuin suomalaiset. Kansa on aikoinaan kokeillut lukuisia variaatioita, joten voidaan sanoa, että nykyinen suomalainen polkka on pitkän kehittelyn ja testauksen tulos ja polkan hienostunein muoto. Suomalainen polkka on nopeampaa kuin alkuperäinen keskieurooppalainen polkka, ja nopeampi rytmi vaatii erilaisen askelikon. Suomen ulkopuolella askelikko tunnetaan myös osassa Viroa ja kuuleman mukaan se on tavattu paikallisesti Latviassa, eräässä Norjan eristyneessä vuonossa ja Uralilla.