Kinnunen muutti 4-vuotiaana Jatkosodan aikana ns. sotalapsena siskonsa Ritvan kanssa etelä-Ruotsiin Simrishamniin. Takaisin Suomeen hän muutti 10-vuotiaana, suomenkielen unohtaneena. Ruotsissa hän oli jo laulanut paljon ja soittanut myös pianoa. Palattuaan hän opetteli teini-iässä soittamaan aluksi haitaria ja myöhemmin kitaraa.

Laulajista Laila Kinnuseen tekivät erityisen vaikutuksen ruotsalainen Alice Babs sekä amerikkalainen Ella Fitzgerald. Vuoden 1955 syksyllä Kinnunen osallistui ensimmäisiin iskelmälaulukilpailuihinsa Helsingin Polilla, ja voitti. Tuolloin hän aloitti myös keikkailun koulutovereidensa yhtyeen solistina. Seuraavana keväänä hän vastasi hanuristi Lasse Pihlajamaan lehti-ilmoitukseen, jossa tämä etsi yhtyeelleen kielitaitoista solistia. Pihlajamaa oli hyvin otettu nuoren tytön lahjakkuudesta, ja kiinnitti Kinnusen yhtyeensä solistiksi. Voitettuaan keväällä 1957 peräti iskelmälaulun suomenmestaruuskilpailussa ulkomaisen sarjan laulullaan Hey mambo (ja sijoittuen kotimaisessa kolmanneksi) kiinnitettiin hänet syksyllä nuorekkaan Scandia-yhtiön artistiksi. Scandiassa oli johtajiensa Harry Orvomaan ja Paavo Einiön toimesta jo kehitetty mittavaan suosioon noussutta ns. jazziskelmää. Tyylin läpimurtona voidaan pitää Brita Koivusen levytystä Suklaasydän vuodelta 1956, jossa säestäjänä oli Olli Hämeen kvintetti. Hämeen yhtye oli jotakuinkin johtavassa asemassa alalla siihen aikaan, ollen jo käytetty levytyskokoonpanokin säestystehtävissä.

Scandian levytyksiin oli jo aiemmin osallistunut vierailevana kapellimestarina ja sovittajana Jaakko Salo, jonka johdolla Laila Kinnunen levytti syksyllä 1957 debyyttinään italialaisen Domenico Modugnon säveltämän iskelmän Lazzarella, Sauvo Puhtilan käännöksenä. Seuraavallekin levylle  tuli ajan buumin mukaisesti laulu Italiasta, Taccanin Chellállá, niinikään Puhtilan käännöksenä Illalla, illalla. Kinnusella oli vaikeuksia saada suomen kielen ääntämyksensä kohdalleen – olihan hän ehtinyt Ruotsin vuosinaan lapsuudessaan jo unohtaa äidinkielensä – ja vaikka tyydyttävään tulokseen lopulta päästiinkin, säilyi Kinnusella kuitenkin suomalaisittain hieman vieraalta kuulostava artikulaatio, mikä varmasti osaltaan myös oli osa hänen persoonallisuuttaan tulkitsijana.