Prompt wies das Polizeidepartement am 30. März 1927 das Gesuch des Palermo um eine Betriebsbewilligung ab. Selbstverständlich liess sich die Abweisung nicht mit der drohenden Konkurrenz für das Stadttheater begründen. Man verwies stattdessen auf die Nähe des Kinos zum Steinenschulhaus, dessen Schüler durch Kinoplakate gefährdet würden.
Als der Regierungsrat den Rekurs des Bauherrn abwies, zog dieser den Fall an das Bundesgericht weiter. Sein Anwalt machte geltend, dass der Widerstand gegen den Neubau dem Konkurrenzneid des Theaters entspringe; dies sei in Basel "ein offenes Geheimnis". Mit Urteil vom 28. Oktober 1927 hiess das Bundesgericht den Rekurs gut. Die Kinder, so die Richter, kämen auf dem Schulweg ständig an Kinos oder ähnlichen Betrieben vorbei und seien diese gewohnt. Am 21. November 1928 nahm das vom Architekturbüro Suter und Burckhardt gestaltete Palermo mit seinen 1'200 Sitzplätzen den Betrieb auf.