Manipulation of deformable objects is a challenging domain in robotics. Although it has been gaining attention in recent years, long-horizon deformable object manipulation remains largely unexplored. In this letter, we propose a benchmark for the bi-manual Shoe Lacing (SL) task for evaluating and comparing long-horizon deformable object manipulation algorithms. SL is a difficult sensorimotor task in everyday life as well as the shoe manufacturing sector. Due to the complexity of the shoe structure, SL naturally requires sophisticated long-term planning. We provide a rigorous definition of the task and protocols to ensure the repeatability of SL experiments. We present 6 benchmark metrics for quantitatively measuring the ecological validity of approaches towards bi-manual SL. We further provide an open-source simulation environment for training and testing SL algorithms, as well as details of the construction and usage of the environment. We evaluate a baseline solution according to the proposed metrics in both reality and simulation.