We introduce a new structural technique for pruning deep neural networks with skip-connections by removing the less informative layers using their Fisher scores. Extensive experiments on the classification of CIFAR-10, CIFAR-100, and SVHN data sets demonstrate the efficacy of our proposed method in compressing deep models, both in terms of the number of parameters and operations. For instance, for the classification of CIFAR-10 images, our method can compress a ResNet56 model with 0.85 million parameters and 126 million operations with 75% and 62% reduction in the number of parameters and the number of operations, respectively, while increasing the test error only by 0.03%.