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