Regression Testing is a time consuming, costly activity used to uncover new errors in existing functionality, after changes have been made to the software. Test case prioritization techniques improve the cost-effectiveness of regression testing by ordering test cases such that the important test cases are run earlier in the testing process. Most prioritization techniques utilize some form of code coverage information to direct the prioritization effort. The various code coverage information used are statements, branches, conditions and blocks. In this work, it has been suggested that, if change coverage can be used, test cases that cover updated part of the software can get more priority. This kind of ranking ensures that the prioritized test cases work better for modified software and thus help in regression testing. Hence, a rank-based coverage criterion making use of both change coverage and statement coverage is introduced. An Optimal Tabu Prioritization algorithm, which utilizes change coverage, is proposed to solve prioritization optimization problem. The Optimal Tabu Prioritization algorithm is evaluated against prioritization using Hill Climbing algorithm and simple Tabu Search based prioritization algorithm. The experiments showed that the Average Percentage Statement Coverage and Average Percentage Decision Coverage of Optimal Tabu Prioritization is 2.57% and 12.55% more respectively when compared to Tabu Search based prioritization algorithm, when only 25% of test cases are executed under resource constraints. © 2016 CRL Publishing Ltd.