Huulipunan historia ulottuu niinkin kauas kuin viidentuhannen vuoden päähän. Muinaisessa Sumerissa nykyisen Irakin alueella murskattiin punertavia jalokiviä ja koristeltiin kasvot ja huulet niiden pölyllä.
Köyhemmät sumerilaiset värjäsivät huulensa punaisella savella tai hedelmien tai muiden kasvien mehulla.
Myös egyptiläiset pitivät värjättyjä huulia puoleensavetävinä ja sivelivät huuliinsa monenlaisia aineita saadakseen punaiset, violetit tai mustat huulet. Jotkin aineista, kuten bromi, olivat käyttäjilleen myrkyllisiä.
Egyptissä sekä naiset että miehet käyttivät huuliväriä, ja värjätyt huulet olivat korkean sosiaalisen aseman merkki. Joissakin sivilisaatioissa huulten värjäämiseen on suhtauduttu torjuvasti ja paheksuvasti.
Esimerkiksi antiikin Kreikassa, keskiajan Euroopan joissain osissa ja viktoriaanisen ajan Englannissa huuliaan maalasivat vain prostituoidut ja muut yhteiskunnan marginaaliryhmät.
Nykyaikaiset huulipunat tulivat markkinoille 1880-luvulla, kun ranskalaiset hajuvesikaupat alkoivat myydä huuliväriä kovina silkkipaperiin pakattuina puikkoina.
Puikot valmistettiin muun muassa talkista, risiiniöljystä ja mehiläisvahasta. Niillä väriä oli niin helppo levittää, että huulipunan käytöstä tuli yhä yleisempää 1900-luvun alussa.
Suosiota edistivät myös ajan muoti-ikonit eli mykkäfilmien tähdet, joilla huulipuna korosti ilmeitä valkokankaalla.