In spite of the remarkable performance, deep convolutional neural networks (CNNs) are typically over-parameterized and computationally expensive. Network pruning has become a popular approach to reducing the storage and calculations of CNN models, which commonly prunes filters in a structured way or discards single weights without structural constraints. However, the redundancy in convolution kernels and the influence of kernel shapes on the performance of CNN models have attracted little attention. In this article, we develop a framework, termed searching of the optimal kernel shape (SOKS), to automatically search for the optimal kernel shapes and perform stripe-wise pruning (SWP). To be specific, we introduce coefficient matrices regularized by a variety of regularization terms to locate important kernel positions. The optimal kernel shapes not only provide appropriate receptive fields for each convolution layer, but also remove redundant parameters in convolution kernels. SWP is also achieved by utilizing these irregular kernels and actual inference speedups on the graphics processing unit (GPU) are obtained. Comprehensive experimental results demonstrate that SOKS searches high-efficiency kernel shapes and achieves superior performance in terms of both compression ratio and inference latency. Embedding the searched kernels into VGG-16 increases the accuracy from 93.53% to 94.26% on CIFAR-10, while pruning 59.27% model parameters and reducing 27.07% inference latency.