Rostrup kirke er opført af granitkvadere med et sengotisk tårn i vest og en udbygning i nord.

Våbenhuset er fra 1869.

Syddøren er bevaret, mens resten af murene synes omsat og forhøjet med teglsten.

Tårnets underdel og udbygning mod nord synes opført af genanvendte kvadere.
I tårnrummet er frilagt to rosetter af kalkmalerier fra 1500 tallet.