Jabal Hafit provides a rare outcrop of important Cretaceous and Tertiary carbonate sequences found throughout the Middle East. This study focuses on permeability estimation from NMR in 72 rock samples from three Middle Eastern carbonate formations, specifically the Rus, Dammam and Asmari formations which are Paleocene to Miocene in age. Our study includes mineralogy, porosity, permeability, NMR, SEM measurements and analyses. We establish a very simple and useful relationship between porosity and permeability for the suite of formations studied. Porosity and permeability form the basis for separating samples into two well defined flow units. NMR measurements are used to define bound and free water based on a T2-cutoff. Desaturation studies show Swir and the corresponding T2-cutoff values vary considerably. We evaluate the Coates and SDR permeability estimators and find the SDR produces better agreement with direct measurements of permeability.