A multiple display environment (MDE) networks personal and shared devices to form a virtual workspace, and designers are just beginning to grapple with the challenges of developing interfaces tailored for these environments. To develop effective interfaces for MDEs, designers must employ methods that allow them to rapidly generate and test alternative designs early in the design process. Paper prototyping offers one promising method, but needs to be adapted to effectively simulate the use of multiple displays and allow testing with groups of users. In this paper, we share experiences from two projects in which paper prototyping was utilized to explore interfaces for MDEs. We identify problems encountered when applying the traditional method, describe how these problems were overcome, and distill our experiences into recommendations that others can draw upon. By following our recommendations, designers need only make minor modifications to the existing method to better realize benefits of paper prototyping for MDEs.