Cryptography is one of the common approaches to secure private data and cryptanalysis involves breaking down a coded cipher text without having the key. Cryptanalysis by brute force cannot be accepted as an effective approach and hence, metaheuristic algorithms performing systematic search can be applied to derive the optimal key. In this study, our aim is to examine the overall suitability of Artificial Bee Colony algorithm in the cryptanalysis of polyalphabetic cipher. For this purpose, using a number of different key lengths in both English and Turkish languages, basic Artificial Bee Colony algorithm (ABC) is applied in the cryptanalysis of Vigenere cipher. In order to improve the ABC algorithm's convergence speed, a modified binomial crossover based Artificial Bee Colony algorithm (BCABC) is proposed by introducing a binomial crossover-based phase after employed bee phase for a precise search of global optimal solution. Different keys in various sizes, various cipher texts in both English and Turkish languages are used in the experiments. It is shown that optimal cryptanalysis keys produced by BCABC are notably competitive and better than those produced by basic ABC for Vigenere cipher analysis.