Antigament era coneguda com Sant Esteve de Mata. La primera vegada que la trobem documentada va ser l'any 974, quan el comte d'Empúries-Rosselló la va donar al monestir de Sant Pere de Rodes. Es va canviar l'advocació durant l'època en que va estar sota la protecció del monestir passat a anomenar-se l'indret com la Selva de Sant Romà o Mata de Sant Romà.

L'església que podem contemplar data del segle XII. Es va construir amb una sola nau coberta amb una volta de canó lleugerament apuntada. El temple està capçat a l'est amb un absis semicircular, que té una finestra de doble esqueixada en la part central.

En el segle XIV es va fortificar el temple, doblant l'alçada dels seus murs, que estan coronats amb merlets. En la façana oest s'hi va construir un matracà. 

La porta d'accés s'obre en el mur oest. Està formada per tres arcs de mig punt adovellats en gradació.

En el segle XVII es va construir un nou temple dins del poble i l'església passa a ser un santuari dedicat a Sant Sebastià i capella del cementiri. Això va fer que s'adossessin al mur sud alguns nínxols i es tapés la finestra de doble esqueixada d'aquest sector. En construir el nou cementiri es van retirar aquests nínxols, retornant al temple el seu aspecte original.