Но не все было так радужно – чем известнее он становился, тем пристальнее за ним следили в руководстве Азербайджана. Буквально подсчитывали, сколько времени он проводит за пределами республики, словно ревновали к другим республикам и городам, особенно к Москве, откуда постоянно звонили, приглашая выступать и на радио, и на телевидении, и в концертах, в том числе и правительственных. При этом совершенно не принималось во внимание, что Магомаев и не думает отказываться от своей родины – на всех афишах он значился как азербайджанский певец, к вящей славе своей республики.
Это наблюдение доставляло все больше и больше проблем и наконец в 1966 году вылилось в серьезное столкновение между руководством Азербайджана и «железной леди» советского министерства культуры Екатериной Фурцевой. Дело в том, что Магомаев должен был участвовать в большом концерте, который советские артисты давали в Париже, на сцене знаменитого театра «Олимпия». Но азербайджанские власти решили наказать его за то, что он, дескать, слишком редко бывает в родной республике. А без их разрешения он за границу поехать не имел права.
Время шло, сроки поджимали, но Магомаев тоже не собирался сдаваться. Он знал, что никакой его вины перед родным Азербайджаном нет, все эти обиды существуют только в воображении руководства, возомнившего о себе невесть что, и когда других способов не осталось, обратился лично к министру культуры СССР, то есть к Фурцевой. Та тянуть не стала и сразу же позвонила в Баку. Сообщила, что кандидатура Магомаева утверждена министерством, что в Париже уже афиши с его именем висят и что их упрямство грозит опозорить весь Советский Союз. Она настаивала и делала это так, как умела одна она – спокойно, но с таким металлом в голосе, что было совершенно ясно – отказать невозможно.
Конечно, азербайджанские власти сдались, и прямо в день концерта Магомаев наконец вылетел в Париж. Выступать пришлось без репетиции, но ему было не впервой преодолевать трудности, поэтому спел он как всегда блестяще. Настолько блестяще, что его хорошо запомнил директор театра «Олимпия» Бруно Кокатрикс, да и не только он – Магомаеву начали поступать предложения о гастролях в Европе. Но советские певцы не имели права вести такие переговоры, за них с западными импресарио общались представители Госконцерта. А они… то ли специально так сделали, то ли от жадности совсем потеряли голову, но запросили такую огромную сумму, что переговоры так и окончились ничем.
Через три года Бруно Кокатрикс все же организовал гастроли Магомаева в Париж. За это время он стал в СССР еще более знаменитым, да и за рубеж его не раз приглашали. Правда, не по всем приглашениям удавалось ездить, потому что выпускали его редко и очень неохотно. Например, на гастроли в финский оперный театр не отпустили и даже в известность не поставили. Поскольку Магомаев получил копию приглашения, он обратился в Госконцерт уже сам. Но там ему ответили, что им эти гастроли невыгодны, поэтому они их не интересуют. Интересы же и выгода артистов во внимание не принимались, их в Госконцерте рассматривали только с одной стороны – как способ добывания валюты. Собственно говоря, почему его и отпустили на вторые гастроли во Францию (на этот раз с Эдитой Пьехой и Ленинградским мюзик-холлом) – там предложили очень хорошие деньги.