В том же году выпускника призвали в ряды Советской Армии. В первый год службы он был батарейным запевалой, затем голосистого солдата перевели в ансамбль песни и пляски Закавказского военного округа. После демобилизации в 1958 году вчерашний солдат решил стать профессиональным певцом. Он устроился лаборантом, чтобы заработать денег на дорогу. В солдатской форме Иосиф уехал в Москву и поступил в Государственный музыкально-педагогический институт им. Гнесиных на вокальный факультет в оперный класс Л. В. Котельниковой.
Три года учебы в институте студент совмещал с работой вокалистом у Марка Местечкина в цирке на Цветном бульваре, где за вечер ему платили три рубля. В то время на арене блистали молодые клоуны Ю. Никулин, О. Попов, и Кобзон тоже мечтал о славе. Как-то раз известный клоун Р. С. Ширман предложил спеть Иосифу песню А. Пахмутовой «Куба, любовь моя!» в спектакле «Карнавал на Кубе». После удачного дебюта в спектакле Иосиф буквально измором взял популярного композитора А. Островского, добиваясь возможности выступить в одном из его концертов. Поначалу именитый маэстро отказывал, но настырный Кобзон звонил ему домой каждый день, и Островский сдался. Талантливого студента заметили профессионалы и стали приглашать на другие выступления.
Вначале Кобзон пел в дуэте с В. Кохно, а затем начал работать самостоятельно. Ему посчастливилось сотрудничать с такими известными советскими композиторами и поэтами, как А. Пахмутова, О. Фельцман, А. Новиков, Р. Гамзатов, В. Мурадели, А. Бабаджанян, М. Фрадкин, С. Туликов, Я. Френкель, Э. Колмановский, Л. Ошанин, М. Матусовский, Р. Рождественский, Е. Долматовский и др. В 1959 году Кобзона взяли солистом Всесоюзного радио, а с 1963 года – певцом «Москонцерта».
Существует легенда, что Л. О. Утесов, услышав Иосифа, произнес фразу: «Бог дал этому парню голос, но послал его очень далеко». Позже, правда, Леонид Осипович смягчился и по-достоинству оценил талант будущего народного артиста.
Первый гастрольный тур Кобзон совершил в 1962 году по стройкам Сибири. В том же году вышла его пластинка песен А. Островского и А. Пахмутовой, а певец выехал в творческую командировку в Венгрию с Э. Колмановским и К. Ваншенкиным. После успешных концертов за рубежом он продолжал выступать с сольными программами по Советскому Союзу, стал лауреатом многих Всероссийских и Всесоюзных конкурсов.
В 1964 году на Международном конкурсе в Сопоте он завоевал главную премию. К талантливому певцу впервые пришла мировая слава. В том же году Кобзону присвоили первое в его жизни звание «Заслуженный артист Чечено-Ингушской АССР». Вскоре в прессе появилось сообщение, что он во время декады культуры в Грозном пьяным врывался в номера к кинозвездам, пытался их насиловать… Коллеги, знавшие, что это ложь, отправили коллективное письмо в редакцию, но оно не помогло. Иосифа на год отлучили от эфира, отменили концерты.
В 1965 году он все же принял участие в международном конкурсе «Дружба», получил первые премии в Варшаве, Берлине и Будапеште. В 1968 году Кобзон – лауреат международного конкурса «Золотой Орфей» в Болгарии. Он также участвовал во многих Всемирных фестивалях молодежи и студентов. В 1973 году уже знаменитый певец наконец-то завершил учебу в «Гнесинке».
Обязательный и трудолюбивый, Кобзон был одним из первых, кто попал на ТВ. В те годы нужно было петь только вживую, без дублей, т. к. в 1960-х годах записей на телевидении не существовало. У других артистов случались проблемы из-за алкоголя, голоса, настроения, а Кобзон всегда был в форме. Проблемы у него возникли в 1970-е, когда попасть на телевидение мешала «пятая графа». Тогда существовала негласная установка «сверху»: «евреев на праздничном экране быть не должно». Сам Иосиф Давыдович утверждал, что председатель ЦТ Лапин лично «не запрещал» Кобзона, а старожилы «Голубого огонька» рассказывали, как Лапин вызывал к себе редактора и говорил: «Зачем нам эти кобзоны?..» Несмотря на это, многие известные композиторы доверяли ему первое исполнение своих песен, и он полностью оправдывал их доверие.
Много раз артист давал концерты в Австралии, Израиле, Японии, США, государствах Европы, Африки, Южной Америки. Он пел русские, украинские, итальянские, испанские, еврейские песни, и публика его очень тепло принимала.
Еще в советские годы Кобзон понял, что любовь к Родине не означает бессребреничество. Чтобы заработать на первую кооперативную квартиру, он поехал с концертами по Сибири и Дальнему Востоку. В следующие гастрольные марафоны по СССР артист отправился, чтобы купить мебель и машину. Постепенно он приобрел и обставил еще одну квартиру, перевез в Москву мать, отчима, братьев, сестру. Затем певец обзавелся еще более престижным движимым и недвижимым имуществом. (Сейчас у артиста есть шикарный офис, большая пятикомнатная квартира, а дача недалеко от Переделкино – настоящая вилла с гектаром земли.) Некоторые знакомые просили денег в долг, потом «забывали» его вернуть, иногда речь шла о солидных суммах.