Multiplication is an essential operation in informatics engineering,for example in cryptography, cryptanalysis, and image processing fields.Researchesabout multiplication algorithmhave been conducted and improved by experts in numerous field,ranging from mathematics, informatics engineering, to electrical engineering. The most popular multiplication algorithm is created by Anatoly Karatsuba in 1960 in Soviet Union. Although it is old and many new multiplication algorithms arise, still this algorithm is chosen for middle to large size number category. Divide and conquer technique is implemented in this algorithm to speed up the multiplication process. The weakness of Karatsuba algorithm is the excessive recursive process,causing a longer execution time. Nikhilam II method is an algorithm founded in India and is included in Vedic Mathematics. Usually,Nikhilam II method is used by common people in India to ease daily multiplication calculation. This method can replace some of the multiplication operationswith addition, therefore it can be more optimum. In this paper, Nikhilam II method is implemented in the base case part of Karatsuba algorithm to reduce the recursive call. Hence, Karatsuba algortihm can be optimized from time execution point of view. As the result, this new algorithm can optimize time execution up to thrice faster than the original algorithm.