L'església va ser consagrada el 22 de gener del 1046 per Bernat, bisbe de Coserans, amb l'autorització del bisbe de Girona. En l'any 1204, Dalmau de Creixell i la seva mare Berenguera, van vendre al priorat de  Santa Maria de Lladó la senyoria feudal de la parròquia. 

El temple romànic va ser profundament reformat entre els segle XVII i XVIII. La seva estructura presenta algunes incògnites, que no es resoldran fins que no es realitzi una campanya arqueològica. A primer cop d'ull, sembla que el temple tenia una sola nau, coberta am b una volta de canó de perfil apuntat i capçada amb un absis semicircular ultrapassat. En la part central del tambor absidal s'obre una finestra d'una sola esqueixada.

En la cornisa, que trobem sota la teulada de l'absis, podem veure una petita flor esculpida. El seu estat de conservació, com el de tota la cornisa, és bastant deficient, motiu pel qual podem imaginar que segurament es van esculpir algunes més, avui desaparegudes.

Alguns estudiosos afirmen que el temple de Sant Martí de Queixàs segueix la tipologia i la manera de construir dels temples nord-catalans de finals del segle X.

L'edifici va ser modificat en el segle XII, quan es construeix la porta d'accés. Està situada en el mur oest i respon a la tipologia característica d'aquesta zona amb tres arcs de mig punt en gradació envoltant un timpà i llinda llisos.

En aquest cas l'arc interior té l'aresta incurvada i aquesta part està decorada amb tres motius florals i un en forma d'espiga.

També presenta una decoració similar el guardapols on veiem dues flors, un cap, una semiesfera, una pinya, una altra fruita i dos motius geomètrics.

En la porta trobem el forrellat i el tirador de tradició romànica. El forrellat i els seus suports estam decorats amb incisions de tipus geomètric. L'extrem del costat dret del forrellat presenta una decoració a base d'un cap de serp..

La següent reforma es va produir entre els segles XVII i XVIII, quan es van afegir capelles laterals, es va redecorar l'interior de la nau i es va construir una torre campanar en l'angle sud-oest.

Les incògnites que presenta el temple fan referència a dos elements que trobem en el costat de tramuntana. Malauradament aquest sector resta ocult per al visitant, doncs hi ha adossada la rectoria. En el mur de ponent d'aquest edifici i adossat a l'església hi ha un fragment amb carreus ben polits i que semblen correspondre a un absis o alguna torre. La seva ubicació, poc corrent, fa dubtar sobre la seva funció original.

L'altre element es troba junt a l'absis, en el que actualment és la sagristia. Té planta circular, a excepció del sector de ponent on té un mur recte on s'obria una gran arcada de mig punt, actualment cegada. Es desconeix que hi havia al altre costat d'aquest arc i que probablement comunicava amb l'absis o torre de ponent, doncs aquest espai està ocupat per dependències de la rectoria, més modernes i que l'han ocultat gairebé en la seva totalitat.

L'estança que ocupa la sagristia està coberta per una cúpula semicircular. Les seves dimensions ens fan pensar que no es tracta de cap absis lateral, però sense cap estudi arqueològic és impossible interpretar quina era la funció per a la que va ser construïda.