Efficient codon optimization with motif engineering. It is now common to add synthetic protein coding genes into cloning vectors for expression within non-native host organisms. Codon optimization is the task of choosing a sequence of codons that specify a protein so that the chosen codons are those used with the highest possible frequency in the host genome, subject to certain constraints, such as ensuring that occurrences of pre-specified ”forbidden” motifs are minimized. Codon optimization supports translational efficiency of the desired protein product, by exchanging codons which are rarely found in the host organism with more frequently observed codons. Motif engineering, such as removal of restriction enzyme recognition sites or addition of immuno-stimulatory elements, is also often necessary. We present an algorithm for optimizing codon bias of a gene with respect to a well motivated measure of bias, while simultaneously performing motif engineering. The measure is the previously studied codon adaptation index, which favors the use, in the gene to be optimized, of the most abundant codons found in the host genome. We demonstrate the efficiency and effectiveness of our algorithm on the GENCODE dataset and provide a guarantee that the solution found is always optimal. The implementation and source code of our algorithm are freely accessible at url{}.