ماریان آندرسون در سال 1930 اولین کنسرت اروپای خود را در تالار ویگمور (Wigmore Hall) لندن اجرا کرد که با موفقیت فراوانی روبرو شد. دهه های اولیه 1930 را در سفرهایی به سرتاسر اروپا سپری کرد، جایی که با تبعیض نژادی شدیدی که در آمریکا تجربه کرده بود، مواجه نشد. در تابستان 1930 به اسکاندیناوی رفت و پیانیست فنلاندی کوستی فهانن (Kosti Vehanen) را ملاقات کرد، شخصی که از آن پس همراه همیشگی و استاد خوانندگی وی برای سالهای متمادی شد.

آندرسون همچنین از طریق فهانن، با سیبلیوس (Jean Sibelius) آشنا شد. پس از آنکه سیبلیوس صدای آندرسون را در کنسرتی در هیلسنکی شنید، عمیقا تحت تاثیر اجرای او قرار گرفت و آنان را به منزل خود دعوت کرد و از همسرش خواست در اتاقی که مخصوص نوشیدن قهوه سنتی بود به افتخار حضور آندرسون شامپاین باز کند.

سیبلیوس به آندرسون پیشنهاد داد که با توانایی که او داد می تواند به روح "نوردیک" (سمبلی وابسته به نژاد مردی قدبلند و سر دراز اسکاندیناوی - Nordic) رسوخ کند. دوستی سریع آنان با کار حرفه ایشان شکوفا شد، برای سالهای بسیار، سیبلیوس آهنگهای فراوانی مخصوص آندرسون ساخت تا او اجرا کند، به ویژه آهنگی جدید به نام "تنهایی" (Solitude) را در سال 1939 به آندرسون تقدیم کرد که این قطعه را برای اجرا در ارکستر تنظیم کرد و در اصل از قطعه "دختر یهودی" ساخته خودش در سال 1906 که موسیقی ضمنی (incidental music) بود، اقتباس نمود.

بشنوید قسمتی از "Hard Trials" را با صدای ماریا آندرسون

در سال 1934 سول هاروک (Sol Hurok)؛ مدیر و برنامه ریز کنسرتها، به آندرسون پیشنهاد قرارداد بهتری را داد از آنچه آرتور جادسون با او بسته بود. هاروک از آن پس برنامه ریز دائم کنسرتهای آندرسون شد و تنها او بود که توانست آندرسون برای بازگشت به آمریکا و اجرا در آنجا متقاعد کند. در سال 1935 برای اولین بار در رسیتالی در تالار شهر نیویورک حضور یافت که مورد توجه منتقدین موسیقی قرار گرفت. پس از آن به مدت چهار سال در سرتاسر اروپا و آمریکا به اجرای کنسرت پرداخت.

با آنکه در این زمان بسیاری از اپراها به وی پیشنهاد ایفای نقش را داده بودند اما او به دلیل آنکه اعتقاد داشت تجربه محدودی در اپرا دارد، از قبول آنان امتناع کرد، گرچه وی چندین اپرا اجرا کرده است که ضبط این آثار جز پرفروش ترین آلبومهای اپرا می باشند.

به همراه سرپرستش فهانن، به روسیه و اروپای شرقی سفر کرد و مجدد به اسکاندیناوی بازگشت، جایی که در شهرها و روستاهای کوچک آن، "تب ماریان" همه را در بر گرفته بود و هزاران مشتاق و طرفدار موسیقی آندرسون منتظر بازگشتش بودند. ماریان خیلی زود، به خواننده مورد علاقه بسیاری از رهبران بزرگ ارکسترهای اروپا بدل شد. در سفر سال 1935 به شهر سالزبورگ، رهبر مشهور ارکستر، آرتور توسکانینی (Arturo Toscanini) به آندرسون گفت: "شما دارای صدایی هستید که در طول 100 سال تنها یک بار شنیده می شود!" او می دانست صدای غنی آندرسون هیچ راهی برای شکست خوردن ندارد. از اواخر دهه 1930 آندرسون سالانه 70 رسیتال را در آمریکا اجرا می کرد.

بشنوید قسمتی از "If He Change My Name" را با صدای ماریا آندرسون

اگرچه در آن زمان کاملا معروف شده بود با این حال متاسفانه همچنان تبعیضهایی که در گذشته به عنوان یک خواننده سیه چرده با آن روبر شده بود ادامه داشت. در سفرهایش در سرتاسر آمریکا اجازه نداشت در هر هتلی که بخواهد اقامت کند و در بسیاری رستورانها اجازه ورود نداشت. در سال 1939 "انجمن زنان آمریکا" واقع در واشنگتون به آندرسون مجوز اجرا در تالار قاون اساسی–کانستتوشن هال (Constitution Hall) را ندادند.