Military, political and economic relationship between China and Russia has grown exponentially over the past two decades and evolved into a strategic partnership. Two recent developments, United States' ”rebalance to Asia” policy and NATO's expansion into Russia's western periphery, have brought the two countries closer on a number of international fronts. In this article we debate China-Russia military partnership in the Asia-Pacific. For this purpose, we offer a comprehensive analysis, including in our scope the Russia-Vietnam relations, China-Russia defense cooperation, and the role of the SCO in the Asia-Pacific. We argue that China and Russia mostly agree with each other on structural issues such as redefining the parameters of international governance. However, they also continue to encounter disagreements and conflicts over conjectural issues such as energy and arms trade. We conclude that in the Asia-Pacific, China and Russia will likely develop a more comprehensive relationship that may have greater practical implications for the region's security and stability.