Находившиеся в то время в Казани антрепренер С. Я. Семенов-Самарский набирал труппу для зимнего сезона в Уфе. Было это осенью 1890 года. К нему явился молодой Шаляпин и попросил взять его в хор. Просьба юноши была уважена, и он отправился служить в Уфу, согласившись на двадцатирублевое жалованье, причем сначала ему было даже предложено поступить на 15 рублей. Шаляпина не испугала и такая ничтожная цифра: столь велики были страсть его к сцене и желание во что бы то ни стало пробиться вперед, и столь ничтожными являлись его жизненные потребности. Что такое 20 рублей в месяц, даже при дешевизне провинциальной жизни? Ведь на эту сумму надо было иметь хоть какой ни будь угол, быть сытым и хоть сколько ни будь прилично одеваться. Но и эти 20 рублей, и первый этап его страннической жизни - служба в Уфе -были еще относительным благополучием в сравнении с тем, что постигло его в следующие годы.
С Уфы началась для Шаляпина полоса жизни, которая теперь должна ему казаться дурным сном, тяжелым кошмаром, до того не верится в действительность всего, что было… В Уфе же Шаляпин впервые, хотя и смутно, мог почувствовать, что недаром заложено в нем страстное стремление к сцене, что где-то на самом дне его души, еще не развернувшейся вполне, как прекрасный, готовый вскрыться цветок, дремлют богатырские силы. Как часто бывает в жизни, счастливый случай и тут сыграл Решающую роль. Была назначена опера “Галька”. Исполнитель партии стольника перед генеральной репетицией внезапно отказался от нее, заменить его было некем, и тогда рискнули обратиться к Шаляпину с просьбой, не попробует ли он спеть стольника. Он согласился, приготовил роль, и уже на генеральной репетиции все были поражены, насколько этот робкий, застенчивый хорист хорошо овладел своей партией. Насту пил день спектакля, 18 декабря 1890 года, знаменательный день в жизни Шаляпина, так как отсюда надо считать начало его подлинной артистической деятельности. Шаляпин спел стольника не только вполне благополучно, но даже с успехом: заключительная ария в первом акте вызвала дружные аплодисменты всего театра, и фонды юного артиста сразу поднялись так высоко, что антрепренер увеличил ему жалованье на целых пять рублей. В дальнейшем ему пришлось еще выступать в той же партии и всякий раз с неизменным успехом, а затем началось и расширение его репертуара. Так, 8 февраля 1891г. в бенефис артистки Террачиано, поставившей оперу Верди “Трубадур”, Шаляпин впервые исполнял роль Фернандо, у которого имеется довольно трудная ария в первом акте, и этот выход молодого артиста также увенчался успехом. Сезон закончился даже его бенефисом, 3 марта, когда Шаляпин исполнял партию Неизвестного в опере Верстовского “Аскольдова могила”.
Вскоре после этого труппа Семенова-Самарского прекратила свои спектакли, члены ее разъехались кто куда, Шаляпин же остался в Уфе, по просьбе местного кружка любителей музыки и драматического искусства, задумавшего собственными силами устроить оперный спектакль, в программу которого вошли сцена у собора из “Фауста” и третья картина первого акта “Демона”, причем Шаляпин исполнял роли Мефистофеля и старого слуги. Затем он концертировал в Златоусте, где пел арию Руслана “О, поле, поле”, арию Сусанина “Чуют правду” и романс Козлова “Когда б я знал”, чем и исчерпывался весь его тогдашний концертный репертуар. В то же время надо было как ни будь обеспечить себе средства к жизни, ибо, оставшись без ангажемента, Шаляпин лишился заработка, и для юного артиста было большим счастьем, что местное общество приняло в нем близкое участие. Председатель губернской земской управы, бывший в то же время руководителем вышеназванного кружка, устроил Шаляпина писцом в управу на жалованье в 35 рублей в месяц. Таким образом, Шаляпин снова очутился в тех же моральных условиях, что и у себя на родине, и разница заключалась только в размерах жалованья: там было 8 рублей, здесь-35, сумма терпимая для человека, привыкшего во всем себе отказывать. Но… опять была унылая служба, тяжелая лямка изо дня в день, нелепые бумаги с утра до вечера, опять горизонт заволакивался темными тучами. Кончилось тем, что Шаляпин попросту сбежал из Уфы и пристроился на 25 рублей в малороссийскую труппу Любимова-Дергача, с которой и принялся кочевать по городам и весям окраин Российской империи, сначала по Волге, потом по всему Закаспийскому краю, и так со всевозможными приключениями добрался осенью 1891 года до Баку, где бросил, наконец эту труппу.