Scandian tuotantopäälliköksi vuonna 1958 kiinnitetystä Jaakko Salosta tulikin keskeinen Laila Kinnusen yhteistyökumppani. Hän vaikutti kappalevalintoihin ja niiden toteutukseen, käännättäen tarvittaessa ulkomaiset tekstit talon luottotekijöillä, joista Sauvo “Saukki” Puhtila ja Kari Tuomisaari olivat käytetyimpiä. Muita sovittaja/kapellimestareita Scandialla olivat Eino Virtanen ja Erkki Melakoski, joista jälkimmäisestä tuli myös Kinnusen uraan vahvasti vaikuttanut henkilö. Alkuvuodesta 1958 Laila Kinnunen siirtyi solistiksi basisti Olli Hämeen yhtyeeseen, mutta hylkäsi yllättäen vuoden kuluttua koko uransa muuttaen silloisen kihlattunsa kanssa Tukholmaan. Hän kuitenkin tuli melko nopeasti takaisin, ja siirtyi Erkki Melakosken orkesteriin vuoden 1960 alusta. Kinnunen oli jo esiintynyt televisiossa, mutta uuden kiinnityksen myötä televisioesiintymisestä tuli säännöllistä. Erkki Melakoski alkoi nimittäin isännöidä vuoden 1960 alussa Mainos-TV:llä alkanutta (aluksi eri nimistä) Kuukauden Suositut -ohjelmasarjaa, jossa hänen yhtyeensä säesti vakiosolistejaan Laila Kinnusta sekä Per-Erik “Pärre” Förarsia. Ohjelma jatkui aina kesään 1966 asti, ja hyvällä syyllä voidaan Laila Kinnusta pitää ensimmäisenä television avulla asemansa vakiinnuttaneena solistinamme.

Laila Kinnusen levytysmateriaali laajeni nopeasti hieman lapsekkaasti lauletuista italoiskelmistä aikuisempaan suuntaan. Mukaan tulivat eurooppalaiset ja amerikkalaiset suosikkisävelmät, vaikkei suoranaisia lastenlaulujakaan unohdettu. Muutamia joululaulujakin hän levytti, joista yksin esittämänsä pari, Petteri Punakuono sekä Talven ihmemaa (1960) olivat aikuisemmasta amerikkaperinteestä Puhtilan kääntämiä. Samana vuonna kollegoidensa Vieno Kekkosen ja Brita Koivusen kanssa taltioidut Tonttuparaati ja Tonttujen jouluyö – myös Puhtilan käännöksinä – ovat puolestaan hieman enemmän lapsille suunnattuja keskieurooppalaisia lauluja.

Mukaan tulivat valssit, jenkat ja tangot, sekä uusi muotimusiikki, brasilialainen bossanova. Nuorisoa ei kuitenkaan tyystin unohdettu aikuisten vuoksi, josta todisteena toinen muotitanssikokeilu, eli twist-levytys Tanssi rakkaani vain/Tietää tähti jokainen (1961). Erkki Melakosken kanssa yhteistyö sujui erinomaisesti myös levytysstudiossa. Vuonna 1962 Melakoski sovitti neljä venäläislaulelmaa Puhtilan käännöksinä, ja kokonaisuudesta muodostui Laila Kinnusen uran vaikuttavimpia kohokohtia. Itsekin hän myöhemmissä haastatteluissa mainitsi Mandshurian kukkulat -esityksen omaksi suosikikseen koko uraltaan. Eikä ole ihme, että tässä yhteydessä taltioitu laulu Tiet sai kaikissa kolmessa Kinnusen poismenon jälkeen toteutuneissa, hänestä kertovissa teatteriesityksissä keskeisen sijan.

1960-luvun puolivälissä tuli yhteistyöhön mukaan sovittaja/kapellimestari Esko Linnavalli, jonka johtamana taltioitiin myös joitakin Kinnusen hienoimpia esityksiä: A. C. Jobimin bossanova Ipaneman tyttö Kari Tuomisaaren tekstillä (1964), Usko Kempin hidas valssi Lennä mun lempeni laulu (1965), ja ruotsalaisen Bo Nilssonin samba Kun (1966), joka on yksi muutamista Kinnusen levyttämistä Juha Vainion varhaisen kauden teksteistä. Linnavallin johdolla tehtiin myös yksi Laila Kinnusen ehdottomista huippuhetkistä, eli Börje Sundgrenin ja Sauvo Puhtilan Muistojen Bulevardi vuonna 1966.

Kyseinen laulu oli mukana Suomen finaalissa Eurovision laulukilpailun karsinnassa, sijoittuen toiseksi. Kinnunen oli ollut maamme ensimmäisenä solistiedustajana “euroviisuissa” vuonna 1961 Ranskan Cannesissa, laulaen Eino Hurmeen ja Sauvo Puhtilan laulun Valoa ikkunassa. Laulu sijoittui 16 maan joukossa kahdenneksitoista. Itä-Euroopan radioliiton vastaavassa kilpailussa hän edusti Suomea Puolan Sopotissa vuonna 1967 Esko Linnavallin ja Juha Vainion laululla En saa.