Так почалася знаменита хрущовська "відлига". Багато репресовані повернулися з таборів раніше терміну. Страчені були реабілітовані, в тому числі і Шалва Окуджава. Повернулася в Москву і мама Ашхен. Їй дали двокімнатну квартиру на Краснопресненській набережній, і незабаром Булат зі своєю сім'єю і братом Віктором переїхав до столиці.
"Відлига" позначалася на всіх: відкрилися нові журнали – "Юність", "Літературна Москва", "Наш сучасник", виникли нові імена в літературі: Роберт Рождественський, Андрій Вознесенський, Белла Ахмадуліна, Євген Євтушенко, Василь Аксьонов. З'явилися художники-модерністи і перші дисиденти. "Ми були першими дисидентськими дисидентами, в той час, коли Сахаров був привілейованим засекреченим фахівцем, Солженіцин – нікому не відомим вчителем, колишнім зеком, а Бродський – школярем", —згадував Євген Євтушенко у книзі "Зустрічі в залі очікування. Спогади про Булаті".
Під враженням повернення мами з табору і на хвилі "відлиги" Булат Окуджава вступив до лав КПРС. Вже через півроку він зрозумів, що, ймовірно, зробив помилку, але шляху назад вже не було.
У Москві Окуджава влаштувався у видавництво "Молода гвардія", а звідти перейшов в "Літературну газету", на посаду завідувача відділом поезії. У "Литературке" Булат познайомився і близько зійшовся зі Станіславом Рассадиным та іншими молодими літераторами. Саме Рассадін став першим, хто дав високу оцінку пісень Булата, коли одного разу той заспівав під гітару. Дійсно, після Олександра Вертинського у Росії нічого подібного не було, тому Рассадіна відразу підкорили і "Ванька Морозів", і "Кулька блакитний", "Надя-Надійка". Він став умовляти одного виконати це в тісному колі, але Окуджава відмовлявся, не надаючи своєму пісенної творчості великого значення. Одного разу він все ж заспівав друзям в "Литературке". Всім сподобалося. і хтось пожартував: "Ну, будеш знаменитий". Він. звичайно, не повірив.
Його перші публічні" концерти відбулися на казенній дачі в Шереметьєво, яку Окуджаві виділили від редакції "Литературки". Він жив там із своєю сім'єю, а ввечері колеги і сусіди збиралися послухати пісні Булата. Це вже стало певним ритуалом —проводити вечори або на дачній терасі, або в лісі біля багаття.
Московська інтелігенція стала навперебій запрошувати Булата в свої будинки. Він співав, його записували на магнітофон, а далі пісні "йшли в народ". Ще ніхто толком і не знав, хто такий Окуджава, а він вже був популярний. У кожному будинку, де був магнітофон, обов'язково були записи пісень Окуджави. А оскільки така розкіш була доступна не всім, щасливі володарі магнітофона відкривали вікно, ставили її на підвіконня, включений на повну гучність, і вся вулиця чула "Ви чуєте, гуркотять чоботи", "Молитву", "Виноградну кісточку".
Композитор Ісаак Шварц у своїх спогадах про Булаті пояснював інтерес до його пісень тим, що в них була "ностальгія за свободу". Пізніше Окуджава і Шварц співпрацювали багато і плідно, а свої перші враження від знайомства з Булатом Ісаак Йосипович описував так: "Він мене буквально підкорив: у нього був бездоганний смак у всьому, що він робив. А в спілкуванні він був простий, навіть ніби сором'язливий… Але цей тихий, небагатослівний, м'який зовні людина, як потім з'ясувалося, міг бути дуже твердим".
Перший офіційний концерт Окуджави, що відбувся в Ленінграді в 1961 році, пройшов з переповненим залом. Влада відразу заворушилися. По команді з Москви в ленінградській газеті "Зміна" з'явився фейлетон "Про ціну гучного успіху". На другий день ця публікація з'явилася і в "Комсомольській правді". А на концерті в московському Будинку кіно Окуджаву освистали, і він був змушений покинути сцену.
"Відлига" закінчувалася. Вже заборонили журнал "Літературна Москва", повсюдно стали закриватися літературні об'єднання, газети все частіше почали переходити з вільного стилю на офіціоз. У 1961 році Окуджаву прийняли до спілки письменників. Тоді ж в альманасі "Тарусские сторінки" була опублікована його повість про війну "Будь здоровий, школяр", яку тут же визнали шкідливою з-за відсутності в ній героїчного пафосу. Більша частина тиражу альманаху була знищена, а Окуджаву після цього ніде не друкували. В цьому ж 1961 році він був змушений піти з "Літературної газети" і став "вільним художником".
Він співпрацював з кінорежисерами Марленом Хуциевым і Петром Тодоровським, писав вірші і прозу, виступав з концертами. Знамениті вечора в Політехнічному музеї рідко обходилися без його участі.
В особистому житті Окуджави теж відбулися великі зміни. З Ольгою Арцимович Булат зустрівся випадково. Їй тоді було двадцять два. а йому – тридцять вісім. Ось як згадує про це сама Ольга Володимирівна: "До дня нашої першої зустрічі я не чула навіть його імені. Коли Окуджава тільки починав ставати відомим, мій дядько, знаменитий фізик Лев Андрійович Арцимович. покликав його у гості – поспівати… От тоді я Булата побачила вперше". Вони стали жити в Ленінграді, а через два роки, восени 1964-го, Ольга народила сина, якого на честь батька назвали Булатом.
Матеріально жили важко. Окуджава їздив в Москву на заробітки. Більшу частину грошей віддавав Галині на сина Ігоря. Не розлучався. тому що вважав своїм обов'язком забезпечити сина квартирою, а для цього треба було дочекатися закінчення будівництва кооперативного письменницького будинку біля метро "Аеропорт". Як тільки квартира була отримана і Галина Василівна там прописалася, вони розлучилися. До його превеликий жаль, після розлучення він втратив зв'язок з Ігорем. Галина не хотіла, щоб він бачився з сином, збиралася заміж, а рік потому раптово померла.
Ольга відразу сказала Булату, щоб він забрав дитину, але той вагався: все-таки молодший. Булат, був ще зовсім маленьким, чи впорається Оля з двома? Але коли він, все ж таки зважившись, поїхав за Ігорем, колишні родичі не віддали сина, пославшись на те, що хлопчик не знає поки про смерть матері і травмувати його не можна. Пізніше, коли Ігор стане важким підлітком, дідусь сам пришле його до батька.
1965 року вийшла велика платівка з піснями Окуджави, видана в Лондоні, неохайно переписана з аматорської магнітофонного запису. У тому ж році Окуджава разом з іншими підписав лист на захист засуджених письменників Андрія Синявського та Юлія Даніеля, і за ним остаточно закріпилася репутація неблагонадійного. Згодом він допомагав Даніелю, який заробляв перекладами поезії Аполлінера, підписував його публікації своїм ім'ям. У 1965 році Окуджава з дружиною і сином переїхали в Москву.
Цьому чимало сприяла мати Булата. Всі колишні лагерницы тісно спілкувалися між собою, допомагали один одному. Ашхен Степанівна мала серед подруг великий авторитет. Вони всі разом взялися за те, щоб "перетягнути" Булата назад у столицю, тому що робота для нього була саме в Москві. Знайшли кооператив, в якому опинилася вільна квартира, зібрали грошей на перший внесок, і Булат з Ольгою справили новосілля у трикімнатній квартирі поруч з метро "Річковий вокзал".
У 1967-му в Югославії на міжнародному поетичному фестивалі в місті Струга за вірш "Олов'яний солдатик мого сина" Окуджава був удостоєний вищої нагороди – "Золотий вінець". Це вірш в Росії було опубліковано лише 20 років потому в "Московському комсомольці". У тому ж році Окуджава з успіхом виступав у Парижі, на наступний рік —у Західній Німеччині. У Москві його офіційні концерти були рідкісні і завжди дуже довго узгоджувалися "нагорі": дозволять не дозволять. Він співав у невеликих Будинках культури, бібліотеках, інститутах – і всюди з аншлагом.
У 1967 році на екрани вийшов фільм Володимира Мотиля "Женя, Женечка і "катюша", поставлений за мотивами повісті Окуджави "Будь здоровий, школяр". Булат Шалвович брав активну участь у написанні сценарію —він склав всі діалоги, хоча Володимира Мотиля неодноразово натякали, що Окуджаву в співавтори брати не варто-за його неблагонадійності. Фільм був прийнятий масовим глядачем "на ура", а пісня "Краплі данського короля пийте, кавалери" пішла в народ.
Наприкінці шістдесятих Булат Шалвович почав працювати над темою декабристів. "Я захопився історичною прозою. Це було чудово – занурюватися у минулі часи, перевтілюватися! .. Звичайно, я тішився на свій рахунок, поки складав. Варто було поставити крапку і перечитати, як починав з прикрістю розуміти, як це слабо. Але мене втішала, підігрівала, раззадоривала віра в те, що вже наступна річ, вже вона-то буде прекрасна", – писав він у Передмові літературного егоїста" до своєї книги "Заїжджий музикант". Він мріяв зняти фільм про декабристе Михайла Бестужеве, але з цим нічого не вийшло: на студії при імені Окуджави у всіх відразу починалася паніка —а раптом будуть неприємності? Він як і раніше залишався в ранзі "неблагонадійного", і більшість державних організацій воліла не мати з ним справ.
В 1970 році на екрани вийшов фільм Андрія Смирнова "Білоруський вокзал". Це був незвично правдивий фільм про війну, який ветерани прийняли так, наче давно чекали. Картина мала величезний суспільний резонанс, а Окуджаві вона принесла всесоюзну популярність і всенародну любов завдяки пісні "Тут птахи не співають…".
В цей час знову починається цькування Окуджави вже як письменника. Критики нетерпимо ставиться до його нових романів: "Мерсі, або Пригоди Шилова" і "Подорож дилетантів". Тривають нападки і на його пісні. У червні 1972 року партійна організація Спілки письменників виключає Окуд жаву з лав КПРС. Приводом послужило те обставина. що в "Нью-Йорк таймі" вийшла стаття, в якій говорилося, що в СРСР немає свободи творчості і прикладом тому – доля Булата Окуджави.
Окуджаву викликали в ЦК і зажадали, щоб Булат Шалвович написав спростування. Окуджава відмовився навідріз: "Мені з собою жити до кінця днів, а вас, не знаю, чи побачу ще раз". Міськком не затвердив рішення первинної партійної організації про виключення Окуджави з лав КПРС: скандал не стали роздувати далі, щоб не давати зайвого приводу західних газет і радіостанцій.
У 1976 році на фірмі "Мелодія" нарешті вийшла перша велика платівка Окуджави. У магазинах-ажіотаж. Мистецтвознавець Лев Шилов так згадував про це:".. .з дверей всі виходили люди з пластинками, і так як обгортковий папір вже давно скінчилася, вони несли пластинки незавернутыми, і на всіх були ці великі портрети Окуджави.