Рождение оркестра напрямую связано с магазином продажи грампластинок в Харбине. Олег Лундстрем был там частым покупателем. Им была приобретена пластинка Дюка Эллингтона, прослушивание которой сподвигло его на создание джазового оркестра.
В 1934 году девять молодых музыкантов принимают решение о создании своего джаз-оркестра. Путём голосования руководителем был избран 18-летний Олег Лундстрем. Оркестр составили: барабаны, один тромбон, два альт-саксофона, две трубы, один тенор-саксофон, на котором играл брат Олега — Игорь Лундстрем, фортепиано — Олег Лундстрем, банджо и контрабас в одном лице. Это был первый состав оркестра Олега Лундстрема. В 1935 году оркестр начинает играть на балах, танцевальных вечерах, а также выступает на местном радио, где его представляют под названием «Зелёный крокодил».
В 1936 году в связи с изменением политической обстановки, а именно продажи КВЖД Японии, отток русских эмигрантов из Харбина увеличился. Оркестр не стал исключением и переехал в город Шанхай. Международный портовый город позволил развиваться коллективу в профессиональной деятельности. Первым их выступлением и местом работы был отель «Янцзы», в последующем один из популярных болл-рум (танцевальный зал) «Мажестик Плаза», позднее элитный болл-рум «Парамаунт». Все эти выступления подняли Лундстрема и его оркестр на вершину популярности. С 1937 по 1940 год оркестр выезжал на летний сезон в курортный город Циндао. Лундстрем начинает работу над аранжировкой русских песен в джазовой обработке. Такие музыкальные произведения, как «Песня о капитане» И. О. Дунаевского, «Чужие города» А. Н. Вертинского, «Катюша» М. И. Блантера и многие другие, приносят ему ещё большой успех на огромном конкурентом рынке биг-бендов. Таких коллективов в городе было более сорока, включая известный оркестр, в котором играл Бак Клейтон. Но, как бы там ни было, пресса Шанхая называла Лундестрема «королём джаза Дальнего Востока».
