Этот «сугубый американец» родился в еврейском местечке Толочин Могилевской губернии, входившей в Российскую империю, а ныне являющейся частью Беларуси, 11 мая 1888 года. Звали его тогда Израилем Моисеевичем Бейлиным. Его отец был кантором (певцом) в синагоге, так что с детских лет Изя, как его называли в семье, приучался к музыке. Он был самым младшим из восьмерых детей (двое сыновей и шесть дочерей). Несмотря на уважаемую в еврейской общине профессию отца, семья жила крайне скромно. Через много лет Берлин говорил, что он вообще не знал, что такое бедность, потому что иной жизни он просто не видел.

Через много лет композитор часто путался, рассказывая, где именно он появился на свет. Чаще всего он называл Могилев, видимо в связи с тем, что о крохотном Толочине в США никакого представления не имели (впрочем, и Могилев был известен только выходцам из России, причем далеко не всем).

Когда ребенку исполнилось четыре года, семья переехала в город Тобольск в Сибири — скорее всего потому, что там жили какие-то родственники, которые обещали помочь в переселении Бейлиных за океан. В некоторых интервью через годы композитор называл Тобольск местом своего рождения, еще более запутывая тех, кто интересовался его происхождением. Разумеется, делалось это непроизвольно — просто Берлин настолько оторвался от своей родины, что забывал, где появился на свет. Берлин вспоминал, что в раннем детстве был свидетелем погрома, во время которого был сожжен его родной дом (где именно это произошло, он не писал): «Я лежу на одеяле на обочине дороги и гляжу, как догорает наш дом».

В 1893 году, получив американскую визу, Бейлины смогли оказаться в Нью-Йорке. Они поселились на Манхэттене, в районе Нижнего Ист-Сайда, который тогда отнюдь не являлся аристократическим местом — там проживала в основном беднота, причем в значительной мере недавно переселившаяся в США из Российской империи. Отец, правда, легко нашел работу по специальности — его звучный голос позволил ему устроиться в местную синагогу.

Вскоре, однако, семья столкнулась с немалыми бедами. У отца пропал голос, он был вынужден стать рабочим на мясном рынке и лишь изредка приносил домой лишние центы, заработанные преподаванием иврита отдельным людям, интересовавшимся еврейской традицией. Когда мальчик учился во втором классе публичной школы, отец умер, и Изе пришлось зарабатывать на жизнь, помогая многочисленной семье. Он разносил газеты, был мальчиком на побегушках в какой-то лавке. На людей производило впечатление, что мальчик почти постоянно пел песни и романсы, услышанные им в соседних ресторанах. Через несколько лет, когда ему исполнилось восемнадцать, он устроился на более стабильную работу официанта в одном из кафе. Именно тогда китайский хозяин кафе в нью-йоркском Чайна-тауне обратил внимание, что его юный официант почти все время поет, и использовал это к своей выгоде.