In this paper, we introduce a network design problem with two-edge matching failures. Given a graph, any two edges non-incident to the same node form a two-edge matching. The problem consists in finding a minimum-cost subgraph such that, when deleting any two-edge matching of the graph, every pair of terminal nodes remains connected. We give mixed integer linear programming formulations for the problem and propose a heuristic algorithm based on the Branch-and-Bound method to solve it. We also present computational results.