Det nya Trosa fick stadsprivilegier 1610, men redan tidigare hade det funnits en kyrka här. Kyrkan hade troligen formen av ett fiskarekapell och ansågs sannolikt otillräcklig när staden fått sina privilegier och blivit ett eget pastorat. En timmerkyrka med ett vapenhus på sydvästra väggen byggdes omkring 1614. Det bestod av ett långhus (19 m långt och 9 m brett) samt ett kor (7m x 7 m). Kyrkan var inte särskilt välbyggd och redan efter ett antal decennier behövde den ersättas av en ny kyrka.
En ny stenkyrka stod klar 1710 och invigdes 1711. På 1750-talet tillkom sakristian och 1895 ersattes spåntaket med plåt. Den senaste restaureringen var utvändig och genomfördes 1978, men förändrade ingenting i själva kyrkorummet. Från början hade kyrkan ett stampat jordgolv, men 1751 täcktes det med gravstenar som tidigare legat på kyrkogården. Det nuvarande stengolvet är från 1981.
Altaruppsatsen och predikstolen skänktes 1711 av Nils Bielke till Gäddeholm och hans maka Eva Horn. Familjen Bielke hade en egen ingång till kyrkan, den sk Greveporten. Den låg på norrsidan mitt emot Söderporten som fortfarande finns kvar. På söderväggen sitter ett litet medeltida altarskåp, Det är ett svenskt arbete från 1400-talets senare hälft och är kvar från den gamla stadskyrkan. Ursprungligen kan det ha tillhört det gamla fiskarekapellet.
Bänkinredningen är från 1945, men efterbildar 1700-talets inredning. Orgelläktaren från 1764 målades av Johan Tecktonius 1832, samtidigt som han målade predikstolen. Orgeln har 24 stämmor och byggdes av Åkerman & Lund 1969. Nummertavlorna är från 1880-talet och krönta med en sörmlandsgrip. Ovanför sakristieingången hänger ett votivskepp från 1700-talet. Där hänger också ett krucifix utfört 1977 av Tomas Almberg.