A detailed study of aeromagnetic anomalies across the Mahanadi Basin on the east coast of India has brought out a concealed basement depression, trending ENE-WSW, in the Rajnagar-Paradeep region. In this article, the aeromagnetic data pertaining to the Rajnagar-Paradeep region are analyzed quantitatively for their basement structure. The inferred basement depression, bounded on the north by a low-angle normal fault and in the south by a steep fault, characterizes the features of a typical half-graben structure. Furthermore, the southern boundary fault of the inferred depression correlates with an ENE-WSW-striking northward-dipping fault in the offshore region. The fact that the marine gravity anomaly also shows discrete lows over this region substantiates the aeromagnetic interpretation.