High resolution 3D coronary artery MR angiography is time-consuming and can benefit from accelerated data acquisition provided by parallel imaging techniques without sacrificing spatial resolution. Currently, popular maximum likelihood based parallel imaging reconstruction techniques such as the SENSE algorithm offer this advantage at the cost of reduced signal-to-noise ratio (SNR). Maximum a posteriori (MAP) reconstruction techniques that incorporate globally smooth priors have been developed to recover this SNR loss, but they tend to blur sharp edges in the target image. The objective of this study is to demonstrate the feasibility of employing edge-preserving Markov random field priors in a MAP reconstruction framework, which can be solved efficiently using a graph cuts based optimization algorithm. The preliminary human study shows that our reconstruction provides significantly better SNR than the SENSE reconstruction performed by a commercially available scanner for navigator gated steady state free precession 3D coronary magnetic resonance angiography images (n = 4).