Vermutlich bereits im 10. Jh. stand an der Stelle der heutigen Kirche ein Sakralbau. Dessen Errichtung dürfte von den Stader Grafen initiiert worden sein. Diese hatten ihren Herrschaftssitz von Harsefeld nach Stade verlegt und residierten in einer Burg auf dem nahegelegen Spiegelberg.
Die Verehrung Kaiser Ottos I., ein Verwandter der Stader Grafen, für die Märtyrerheiligen Cosmas und Damian führte zum Namen der Kirche: Ss. Cosmae et Damiani. Schriftlich erwähnt wird er erstmals 1132.
Den Kern der Backsteinkirche bildet ein einschiffiger Saalbau aus dem 13. Jh. Nach mehrfachen Umbauten zwischen dem 13. und dem 17. Jh. präsentiert sich St. Cosmae heute mit dreischiffigem Chor und achteckigem Vierungsturm. Neben St. Wilhadi ist sie die einzig erhaltene Kirche im Altstadtbereich.
Der große Stadtbrand von 1659 vernichtete die Innenausstattung, die Dächer und den Turmhelm. Die Instandsetzung leitete der Ratszimmermeister Andreas Henne. Er fertigte auch den barocken Turmhelm an. Seit 1684 prägt er die Silhouette Stades.
Das Innere der Kirche prunkt mit der Barockorgel aus der Werkstadt von Berendt Huß. Er baute sie mit seinem Gesellen Arp Schnittger zwischen 1668 und 1675. Schnittger, der auch die (nicht erhaltene) Orgel in St. Wilhadi fertigte, gilt als einer der berühmtesten Orgelbauer seiner Zeit.
Nicht zum Originalbestand gehört der Gertrudenaltar. Der spätgotische, um 1500 entstandene, Flügelaltar stammt aus der 1834 abgebrochenen St. Nicolai-Kirche. Die Mitte ziert die Figur der hl. Gertrud. Beim von Christian Precht 1674-1677 geschaffenen barocken Hauptaltar dominiert ein Kreuzigungsrelief die Mitte, darüber befindet sich ein Aufsatz mit der Grablegungsszene.