Data from a monitored segment (about 20 vessels) of the fleet of about 6000 small vessels (less than 15 meters length overall) operating bottom-set gillnets for cod (Gadus morhua) and monkfish (Lophius piscatorius) in the Norwegian coastal zone were used to estimate the bycatch rates of harbour porpoise (Phocoena phocoena), harbour seal (Phoca vitulina) and grey seal (Halichoerus grypus). Bycatch was estimated using the traditional stratified ratio technique and a GLM-based approach. Bycatch rates were then applied to the landing statistics for the target species for the whole fleet to estimate total bycatch. The stratified ratio estimates ranged from 2211 (CV 0.16) to 3218 (CV 0.17) harbour porpoises, 459 (CV 0.24) to 565 (CV 0.18) harbour seals and 68 (CV 0.27) to 128 (CV 0.41) grey seals. In the model-based approaches, estimates ranged from 2317 (CV 0.16) to 3218 (CV 0.17) harbour porpoises, 424 (CV 0.13) to 600 (CV 0.31) harbour seals and 83 (CV 0.36) grey seals. There were difficulties fitting the models, and the design-based estimators might be considered “best”. Unless the population of harbour porpoise along the Norwegian coast exceeds 176,500 animals, then current levels of harbour porpoise bycatch are unsustainable. Current levels of harbour seal bycatch (coupled with current hunting quotas) are most likely unsustainable. Estimates for grey seal bycatch based on CRF data were not considered reliable, because of insufficient data and the possibility of seal misidentification.