In this paper, we aim to develop a new innovative warehouse design that provides savings for order picking operation which is the most costly and the most related operations with the order delivery time in warehouses. For this purpose, we propose a Discrete Cross Aisle Warehouse Design layout as an alternative to traditional 2-block warehouse layout. In this proposed layout, linear middle cross aisle is designed as a discrete structure (one tunnel on each pick aisle). Harmony search algorithm is used to find an optimal tunnel positions that minimize the average tour length under randomized storage policy by searching the space of all possible designs. In order to calculate average tour length on a proposed design, an algorithm that solves order picking problem optimally in polynomial time is presented. Computational experiments show that optimum designs have the same layout with the traditional 2-block design for small size order lists. As the number of locations to be visited increases, we propose new tunnel allocations that present up to 5% less travel than that in 2-block traditional layout. (This research is supported by TUBITAK (The Scientific And technological Research Council of Turkey) grant 214M220.)