Muzeum mieści się w zabytkowym poewangelickim kościele pod wezwaniem św. Piotra i Pawła, położonym w centrum miasta, tuż obok portu. Część frontową wieńczy niewysoka, drewniana wieża, skąd roztacza się piękny widok na miasto, port i plażę od strony Zatoki Puckiej.
Pierwsza wzmianka o kościele pochodzi z 1417 roku, kiedy pełnił on funkcję kościoła parafialnego w Nowym Helu, jak wówczas nazywała się osada, z której powstało obecne miasto. W 1525 roku został przekształcony w świątynię protestancką, ponieważ większość mieszkańców przeszła na wyznanie ewangelickie.
W 1572 r. pożar miasta ogarnął także wieżę kościoła. Została ona później odbudowana i pełniła funkcję latarni morskiej. W ciągu XVIII wieku silne sztormy i wzburzone fale mocno podmywały skarpę na której stoi kościół. Do katastrofy doszło w 1861 roku, kiedy to część frontowa budynku wraz z wieżą obsunęła się do morza.
W dwa lata później przystąpiono do naprawy ocalałej części budowli. Kościół uzyskał wtedy kształt bliski dzisiejszemu, choć różniący się zasadniczo wyglądem wieży. Ta ówczesna została rozebrana w czasie wojny obronnej we wrześniu 1939 roku. Kościół ucierpiał w wyniku działań wojennych w 1945 r. i został odrestaurowany w 1959 roku. Ponieważ w Helu nie działała już wtedy parafia ewangelicka, budynek pokościelny zaadaptowano na cele muzealne.
W 1972 roku obiekt przekazano Narodowemu Muzeum Morskiemu w Gdańsku, które utworzyło tam swój oddział – Muzeum Rybołówstwa.