1984 trafen sich in einem viel zu kleinen Wohnzimmer knapp ein Dutzend Leute und planten ein Kommunales Kino für Mainz. Es waren Filmleute, Künstler, Literaten und Fernsehredakteure. Letztere brachten eigene Erfahrungen aus anderen Städten und viele Tips mit. Lange wurde beraten, wie ein solches Vorhaben anzugehen sei, welche Rechtsform am Günstigsten wäre und wie die Programmkonzeption aussehen soll.
In den 70er Jahren gingen solche Kinogründungen wie eine Welle über das Land, es lagen also schon Erfahrungen vor. Mainz und Rheinland-Pfalz hatten den Anschluß an die Medienentwicklung verpaßt. Die meisten anderen Städte und größeren Gemeinden hatten bereits Kommunale Kinos gegründet - als städtische Einrichtung, als Volkshochschulabteilung oder in der Trägerschaft eines Vereins.
Wir entschlossen uns, nach Rücksprache mit Mainzer Kommunalpolitikern, für das Vereinsmodell. Unser Vorbild war das Kommunale Kino Freiburg. Nach über einem Jahr Vorbereitung wurde schließlich der Verein Arbeitsgemeinschaft Stadtkino e.V. gegründet, der sich die Einrichtung und den Betrieb eines Kommunalen Kinos zum Ziel setzte.
1985 beschloß der Stadtrat der Arbeitsgemeinschaft Stadtkino e.V. die (eigentlich städtische) Aufgabe der kommunalen Film- und Kinoarbeit subsidiär zu übertragen. Dieser Auftrag war der offizielle Start für die Etablierung eines Kommunalen Kinos in Mainz.
In den darauffolgenden Jahren wurden unter dem Namen "Stadtkino" an wechselnden Spielorten Filmprogramme angeboten, während parallel zusammen mit der Stadt Mainz ein fester Standort gesucht wurde. Letzteres entwickelte sich zu einer Odyssee durch Hallen, Keller und andere Leerstände.
Im Jahr 1990 beschloss der Stadtvorstand das Kommunale Kino neben den Mainzer Kammerspielen auf einer Etage im Proviantmagazin unterzubringen. Ein Jahr später wurden die hierfür vorgesehenen Haushaltsmittel umgewidmet.
Im Jahr 1994 wurde im Institut Français im Schönborner Hof das CinéMayence eröffnet. Den französischen Namen für unser Kino wählten wir als Hommage an unsere Gastgeber.