Viologen-based liquid electrochromic mixtures provide high performance in terms of optical contrast and response time. However, their use in flexible ECDs is quite limited due to the risk of leakage and difficult manufacturing and handling. Herein, it is demonstrated that the incorporation of viologen-based electrochromic mixtures into paper-matrix is a promising solution to overcome the mentioned issues. The performance of flexible paper-based devices using both water-free and water-based formulations containing viologens is assessed for the first time and compared with paper-free devices. The benefits of using paper on the homogeneity, life-time (operating devices above 1000 redox cycles) and robustness against bending (operating devices above 200 bending cycles) is proven: while short-circuits, inhomogeneous coloration and ITO-etching usually occur in the paper-free devices, these concerns are avoided when the liquid mixtures are embedded within the paper-matrix while keeping the good electrochromic performance typically provided by liquid formulations. Additionally, a patterned bi-chromic (blue-green) device is presented as a proof-of-concept to show the potential of these paper-based systems in the field of flexible EC displays.