Mieszkając w Sydney rozpoczęła karierę muzyczną występując w miejscowym zespole Decoder Ring – wtedy jeszcze pod swoim własnym nazwiskiem. Jako wokalistka i klawiszowiec nagrała z nimi dwa albumy.
W 2007 roku przeniosła się za ocean, do USA. Zamieszkała w Kalifornii. 24 września 2008 roku wydała swój debiutancki album, zatytułowany „Lenka”. Artystka przyjęła taki właśnie pseudonim artystyczny – jest to typowe czeskie imię. Album dotarł do piętnastego miejsca na australijskiej liście ARIA chart. Znalazł się tak że na liście Billboard 200 w USA.
Singlem, który promował płytę była melodyjna i łatwo wpadająca w ucho piosenka „The Show”. Łatwo można w niej dostrzec wpływy takich gwiazd jak Regina Spektor, Feist, Yael Naïm czy Eddie Brickell. Utrzymana jest w stylu pop/un-folk. Utwór został wykorzystany w reklamie sklepu odzieżowego „Old Navy”. Pojawił się również w programie telewizyjnym „Ugly Betty” oraz jako Free Single of the Week w iTunes Store. Nagranie cieszy się także dużą popularnością na portalu YouTube, gdzie często jest wykorzystywana jako podkład do alternatywnych filmików w wykonaniu społeczności. Obecnie fragment piosenki wykorzystuje jedna z komercyjnych telewizji do promocji wiosennej ramówki.
Kolejne nagranie artystki, "Trouble Is a Friend" zostało użyte w jednym z odcinków serialu "Chirurdzy".
Niemal po dwóch latach na sklepowe półki trafił drugi album Lenki, zatytułowany po prostu "Two". Album to zbiór 11 melodyjnych, smutnych i wesołych piosenek w charakterystycznym, śpiewnym stylu do którego przyzwyczaiła nas już wokalistka na poprzedniej płycie. Jednak w przeciwieństwie do poprzedniej płyty, tym razem Lenka mocniej postawiła na elektronikę. Przy nagrywaniu albumu współpracowała między innymi z Guyem Sigsworth'em, w świecie muzyki znanym głównie dzięki współpracy z Madonną i Bjork. Wśród producentów znaleźli się równiez Ben Allen (Animal Collective, Gnarls Barkley) oraz Eg White (Adele). Inspiracją dla płyty była prawie roczna trasa koncertowa, przeprowadzka z Australii do Ameryki oraz zaręczyny z Jamesem Gulliverem Hancockiem (który od początku odpowiada za wizualną stronę płyt, teledysków i koncertów Lenki). Płytę "Two" promował "Roll With the Punches" oraz pierwszy oficjalny singel z płyty "Heart Skips A Beat".
Regina Spektor • Feist • Yael Naïm • Madonna • Schiller