Однако Катерина ещё долго была связана с цирком, где в 1950 г. впервые вышла замуж за жонглёра Эрика ван Арко, который затем стал её менеджером. «Я начала записываться в 1958 г., это была джазовая пластинка на 78 оборотов с известным оркестром Курта Эдельхагена. Следом я записала „single" с трубачом Четом Бейкером в Германии на „Polydor", это были тоже джазовые стандарты. Я провела ряд концертов с Эдельхагеном в Париже и выступала с ним на джаз-фестивале во Франкфурте. Два концерта у меня были с Джерри Маллигеном и снова записи с Четом Бейкером («Cat and Chet»).
Первой певицей для меня всегда была Билли Холидэй, и, конечно, я восхищалась Эллой Фитцджеральд и Пегги Ли. Но я никогда не брала за образец кого-либо из них конкретно и никого не копировала. Мне всегда нравился инструментальный джаз, и я хотела, чтобы мой голос звучал как инструмент.
Поэтому все интервалы с оркестром я обычно пела с трубами, очень высоко. Это интересно, и я счастлива, что у меня большой диапазон, но это не всегда необходимо. Я всё же предпочитаю петь спокойные песни с хорошим текстом, и людям это нравится».
После записей на пластинках пришло телевидение. «Меня стали всюду приглашать, и в 1955-1956 гг. я работала в Штатах, где познакомилась со всеми своими кумирами. Затем были кинофильмы — начиная с 1954 г. я снялась в двенадцати музыкальных картинах в Германии, Франции и Италии».
Её величайшими хитами в те годы были «Ganz Paris», «The Breeze And I», «Malaguenja», «Flamingo», «Harlem Nocturne» (с оркестром Вернера Мюллера). В 1965 г. по анкетам профессионального журнала «Musikmarkt» Валенте была признана лучшей европейской певицей. Любопытна оценка Катерины Валенте выдающимся американским критиком Леонардом Фезером. В своей монументальной «Энциклопедии джаза» (1960) он писал: «Несмотря на то, что её знают в основном как популярную артистку из мира кино и эстрады, а не как джазового исполнителя, она в большей степени именно джазовая певица, чем многие другие вокалисты, которых так называют в США. Её музыкальная концепция, фразировка и тембр просто исключительны».
В течение нескольких лет в Париже регулярно выходила специальная телепередача под названием «Bonjour, Catherine!».
«А в начале шестидесятых я впервые поехала в Бразилию и встретилась там со всеми людьми босса-новы — то были Антонио Карлос Жобим, Жоао Жильберто, Луис Бонфа. В этой прекрасной музыке есть свинг, мелодия и поэзия, и я решила переключиться на босса-нову, записав несколько альбомов. Именно тогда я перешла с джазовой гитары на концертную».
