Zgradu u kojoj se nalazi Kino Europa izgradila je 1925. imućna obitelj Müller. Kao nasljednici najveće zagrebačke ciglane na Kustošiji, braća Alfred i Leo podigli su zdanje u današnjoj Varšavskoj.
Njihov je otac, također Alfred, još 1913. sagradio Kino Helios, gdje je danas kazalište Gavella. Nacrt za izgradnju kina Balkan i trgovačke stambene zgrade naručio je 1924., pa prepustio posao u ruke sinova.
Nacrte je za kino Balkan izradio Srećko Florshuetz. Osim što su Mullerovi shvatili unosnost posla puštanja filmova, jedan od njih imao je zanimljiv motiv. Leo Muller bio je filmofil, pa se i sam kao glumac pojavio u nekim prvim domaćim filmovima. Njegova je vizija bila napraviti najljepše, najvažnije i najmodernije kino na ovim prostorima.
Projekcijom filma “Nibelunzi” i domaćeg ostvarenja “Dalmacija, zemlja sunca”, Kino Balkan-Palace svečano je otvoreno 8. travnja 1925. U to je vrijeme primalo 1100 ljudi, koliko je bilo sjedala, podijeljenih u lože, mezanin, prvo i drugo mjesto.
Novine su o kinu pisale kao o hali, pogodnoj i za koncerte te ostala kulturna zbivanja. Naime, u podnožju se pozornice nalazio prostor za orkestar. Filmsko je platno bilo uokvireno širokim zlatnim ramom, a svako je sjedeće mjesto bilo označeno brojem.
Dok je izvorni interijer kina očuvan, zamjenom sjedala broj sjedećih mjesta smanjen je na 500. Iako je pročelje bilo jednostavno i bez puno uresa, interijer kina je bogat. U luksuznoj je čekaonici u prizemlju bio smješten buffet “za prva i ostala mjesta”. Poseban detalj vodoskok je kipara Sunka, izrađen od umjetnog kamena.
Današnje ime Europa, Kino Balkan dobilo je preimovanjem 1990-ih. U čast obitelji koja je kino dala podići, dvorana Muller dobila je svoje ime. Prije no što je otvoreno kino, Zagrepčani su na toj lokaciji posjećivali restoran Lobe-Krizmanić.
Početkom 2008. prostor kina dodijeljen je Zagrebačkom Film Festivalu u namjeri da ono postane regionalni centar filma i sedme umjetnosti.
