Phase contrast (PC) cardiac MR is widely used for the clinical assessment of blood flow in cardiovascular disease. One of the challenges of PC cardiac MR is the long scan time which limits both spatial and temporal resolution. Compressed sensing reconstruction with accelerated PC acquisitions is a promising technique to increase the scan efficiency. In this study, we sought to use the sparsity of the complex difference of the two flow-encoded images as an additional constraint term to improve the compressed sensing reconstruction of the corresponding accelerated PC data acquisition. Using retrospectively under-sampled data, the proposed reconstruction technique was optimized and validated in vivo on 15 healthy subjects. Then, prospectively under-sampled data was acquired on 11 healthy subjects and reconstructed with the proposed technique. The results show that there is good agreement between the cardiac output measurements from the fully sampled data and the proposed compressed sensing reconstruction method using complex difference sparsity up to acceleration rate 5. In conclusion, we have developed and evaluated an improved reconstruction technique for accelerated PC cardiac MR that uses the sparsity of the complex difference of the two flow-encoded images.