Motion is a perpetual challenge in cardiac MRI: for comfortable free-breathing exams, both cardiac and breathing motion need to be resolved. Self-gating approaches have been proposed to automatically bin MRI data into appropriate motion states. Here, we propose a new combined parallel imaging/compressed sensing reconstruction for such multi-dimensional datasets. This method, termed XD-NLINV, solves the non-linear parallel imaging problem, simultaneously estimating images and coil sensitivities. This assures efficient use of the available data and removes the need for pre-calculating the coil profiles. We present initial results showing high image quality for self-gated cardiac short-axis data, resolving both breathing and cardiac motion.