L'église Saint-Cyrille-Saint-Méthode a été érigée, à partir 1935, dans le cadre des Chantiers du Cardinal. L'architecte en est J. Laffilée. Mise à part la construction d'églises dans le centre de Paris, le but des Chantiers est de construire des édifices cultuels de taille moyenne dans les arrondissements périphériques pour lutter contre la déchristianisation.
Les quartiers Est de Paris, comme les quartiers Nord, sont proches de la banlieue industrielle et ouvrière. Parfois fort peuplés, mais peu riches, ils ne peuvent contribuer à l'érection de lieux de culte. C'est pourquoi l'ornementation est souvent réduite au minimum. Les grandes verrières abstraites sont de Paul Bony (1958).
La construction de Saint-Cyrille-Saint-Méthode s'interrompt avec la seconde guerre mondiale et reprend en 1953. Elle est consacrée en 1962. L'église principale de la paroisse, Saint-Germain-de-Charonne, a été très longtemps fermée. C'est alors Saint-Cyrille-Saint-Méthode qui a tenu ce rôle.