Но такие заказы были редкими и денег приносили не много. На протяжении пяти лет Муха страдал от финансовых трудностей: порой голодал, жил в долг, долго и тяжело болел. В тот период основной заработок Мухе приносили иллюстрации, которые ему заказывали популярные журналы. Он также иногда подрабатывал, давая частные уроки живописи. Вспоминая об этом периоде, друзья Мухи рассказывали, что, несмотря на многочисленные проблемы и неурядицы, Альфонс был вежливым и уравновешенным человеком и неунывающим оптимистом, умевшим «держать удары». В Париже Альфонс Муха впервые занялся оформительством, установил связи с издательствами, начал создавать обложки и иллюстрации. Писал он маслом, а его живопись переводили на язык ксилографии. Первый его опыт в этой области – рисунок для обложки журнала «Маленькая французская иллюстрация» (Petit Francais illustré). Он сотрудничал в журнале «Народная жизнь» (La Vie populaire), в воскресных изданиях газет «Фигаро» (Le Figaro illustré) и «Парижская жизнь» (La Vie Parisienne). Он также публиковался в журнале «Злата Прага» (Zlata Praha), работал он и чешский живописец, график и иллюстратор Войцех Прейсиг. Поворотным моментом в судьбе моравского гения стал 1894 г., когда накануне Рождества он получил от театра «Ренессанс» и владельца типографии де Бруноф, с которым он поддерживал деловые отношения, заказ на афишу премьеры спектакля «Жисмонда» с участием великой Сары Бернар. В ближайший вечер де Бруноф и Муха отправились в театр «Ренессанса», в котором играла Сара Бернар. «Сара была великолепна», – вспоминал Муха. Он тут же сделал наброски в своем альбоме. К 27 декабря 1894 г. афиша была готова. Выполнена она была в технике многокрасочной литографии. На афише во весь рост была изображена актриса. Восхищенная Сара Бернар пожелала познакомиться с неизвестным художником, и по ее настоянию он получил место главного декоратора театра. Саре Бернар настолько понравился творческий метод Мухи, что она подписала с художником контракт на шесть лет, в течение которых Муха рисовал не только театральные афиши к спектаклям с участием актрисы, но и работал над костюмами и декорациями к ним. С Сарой Бернар Муха был связан не только рабочими отношениями, но и личными, став на некоторое время ее любовником. В феврале 1897 г. в Париже, в помещении частной галереи La Bordinière, открылась его первая выставка – 448 рисунков, плакатов и эскизов. Она пользовалась невероятным успехом, и вскоре жители Вены, Праги и Лондона также получили возможность посмотреть работы Мухи. В эти годы он также приобрел широкую известность как автор этикеток и виньеток разнообразных товаров – от шампанского и бисквитов до велосипедов и спичек, а также как дизайнер ювелирных украшений, интерьеров, предметов прикладного искусства (ковры, портьеры). От заказов не было отбоя. Газеты писали о феномене Мухи, в Париже даже появилось новое понятие – «La Femme Muchas» («Женщины Мухи»). Роскошные, чувственные и томные «женщины Мухи» тиражировались моментально и расходились тысячными тиражами на плакатах, открытках, игральных картах… Кабинеты светских эстетов, залы лучших ресторанов, дамские будуары украшали шелковые панно, календари и эстампы мастера. В этом же стиле были созданы красочные графические серии «Времена года», «Цветы», «Деревья», «Месяцы», «Звезды», «Искусства», «Драгоценные камни», которые до сих пор тиражируются в виде арт-постеров и подвергаются беззастенчивому плагиату на всех уровнях. Одно из известнейших парижских графических издательств, «Шампенуа» (Le Champenois), заключило с ним эксклюзивный контракт на произведения его прикладного творчества.