Món cá thối truyền thống không thể thiếu trong các bữa ăn của người Na Uy được thực hiện một cách hết sức cầu kì và kĩ lưỡng. Những con cá ban đầu sẽ được loại bỏ xương, sau đó ướp muối và phơi khô trong vài tuần cho tới khi nó rắn lại và có mùi thối. Tiếp theo, người ta sẽ ngâm nó trong dung dịch kiềm nhiều ngày tiếp theo để da cá phân hủy thành màu bàng bạc và thịt cá cũng trở nên chảy nước nhơn nhớt và bốc mùi.
Đáng chú ý hơn, trong quá trình bị ngâm trong dung dịch kiềm, thân của cá sẽ phình to lên và hàm lượng protein bị giảm hơn 50% khiến cá tuyết trông giống như thạch. Để có thể ăn được tiếp sau đó, người ta sẽ ngâm trong nước lạnh từ 4 đến 6 ngày (cũng thay nước hàng ngày).
Thịt cá thối có vị cay và những món ăn kèm nó rất đa dạng, từ thịt xông khói, thịt lợn cho đến nước chấm hay mù tạt. Cho đến giờ, nhiều người vẫn thích ăn kèm món này với bơ tan chảy. Khoai tây, đậu Hà Lan khô, ớt hoặc bánh mỳ cắt lát cũng được nhiều người lựa chọn ăn kèm. Ở miền Bắc Na Uy, người ta còn ăn kèm với pho mát dê tan chảy.
Lịch sử của món cá thối bắt nguồn từ những người Viking. Theo truyền thuyết, những người Vikings đã cướp bóc, đốt cháy một ngôi làng đánh cá, trong đó có cả giá phơi cá tuyết khô. Liền sau đó, dân làng quay trở lại đổ nước vào giá đỡ để dập lửa. Tro bao phủ cá khô, sau đó trời mưa khiến cá bị chôn vùi trong đống tro tàn được ngâm trong dung dịch kiềm. Dân làng ngạc nhiên khi thấy con cá khô thay đổi và trông giống như cá tươi. Họ rửa cá trong nước và đun sôi. Một người dân làng đã dũng cảm nếm thử và tuyên bố là "không tệ". Từ đó đến nay, món ăn này đã trở thành món truyền thống của người Na Uy.
Trên thực tế, món ăn này phổ biến tại Mỹ hơn cả ở Na Uy. Thịt cá thối được tiêu thụ ở Wisconsin (Mỹ) nhiều hơn so với ở Na Uy. Ở Mỹ, cá thối đông lạnh có sẵn tại một số chợ cá và cửa hàng ở Bắc Âu. Những người Mỹ gốc Na Uy thường ăn món này trong Lễ Tạ ơn và Giáng sinh. Nhiều gia đình Na Uy còn thay thế nó cho gà tây vào dịp Giáng sinh.