После нескольких месяцев работы с Джастином, Ашер и Скутер Браун смогли связать его с L.A. Reid, американским музыкальным продюсером, одним из основателей лейбла LaFace Records, известным за открытие Outcast и TLC.
L.A. Reid подписал с Джастином контракт 360 с Island Records. Джастину только исполнилось тринадцать лет. С этого момента все изменилось. Вскоре после этого его мать переехала в Атланту, чтобы он мог работать над музыкой полный рабочий день и теперь официально состоять в крупном лейбле. Карьера Джастина началась почти сразу. Жили они в квартире. В начале своей карьеры Джастина они часто снимали жилье в аренду, чтобы быть ближе к рабочим площадкам и студиям, а также для удобства работы с командой Скутера Брауна. В дальнейшем, по мере роста популярности, его жилищные условия улучшались, но первоначально они с Пэтти действительно проживали в арендованной квартире в Атланте.
Его дебютный сингл One Time вышел в начале 2009 года после нескольких месяцев записей и подготовок. Это был R&B и поп-сингл, написанный известным писателем Tricky Stewart. Этот же парень был ответственным за трек Бейонсе Single Ladies и Мэрайи Кэрри Obsessed. Фидбек на первый трек Джастина был довольно безумным. Его первая песня попала на номер 17 в Billboard Hot 100 в США и номер 12 в Канаде. Для первого трека в истории артиста это был невероятный успех. Вскоре он был даже сертифицирован платиновым в нескольких странах.
Позже, в том же году 6 октября, он выпустил One Less Lonely Girl – еще одну поп-R&B песню, которая взлетела в чартах как сумасшедшая. Когда эта песня достигла 16-го места в Америке, стало понятно, что Скутер прав. Джастин Бибер был рождён, чтобы быть звездой. Затем, когда они отправили его на обычное PR-интервью нового артиста, все пошло еще лучше, чем они могли себе представить. Хоть Скутер и обнаружил Джастина на YouTube, он был не единственным, кто это сделал. Интернет-фанбаза Джастина была безумно мощной, музыкальная индустрия еще не видела такого уровня. Во многих отношениях его история выглядела как план действий для артистов по завоеванию признания в соцсетях.
На самом деле, говорят, что именно благодаря вовлеченности фанатов Джастин смог получить возможность попасть на такое большое количество интервью и шоу. Когда он пошел к Эллен Дедженерес в первый раз летом 2009 на интервью, это именно подписчики Твиттера Джастина убедили Эллен пригласить нового музыканта на шоу.
Тем самым Эллен в свою очередь также сыграла немаловажную роль в карьере Джастина Бибера. В то время Эллен действительно была проводником интернет-культуры в популярную культуру. Если бы какой-нибудь родитель опубликовал видео на YouTube как, например, он запускает своего ребенка в космос, вся семья непременно сразу бы оказалась на шоу Эллен и, вероятно, они бы даже получили большой подарочный билет в Мейси или что-то в этом духе.
Джастин в этот момент был секретом YouTube, о котором женщины поколения Х из Америки должны были узнать. В какой-то момент компиляция всех его выступлений на ее шоу за годы насчитывала более З часов, что больше, чем первая часть фильма Wicked с Арианой Гранде и Синтией Эриво.