The Korean registered Oyang 70 activated a distress beacon and then made a mayday call early in the morning about 400 nautical miles (740 km) east of New Zealand's South Island.
A nearby trawler rescued 45 crew members from life rafts.
"We have so far recovered five life rafts but have been advised there was a sixth life raft on board. We remain hopeful of locating the three missing men," said Mike Roberts of New Zealand's Rescue Coordination Centre in a statement.
A New Zealand airforce plane was helping to search for the missing men, who include the trawler's captain. Conditions in the area were described despite fog.
The three dead crew were identified as Indonesians.
There are no details on what caused the sinking of the 82 metre (270 feet) vessel, chartered by a New Zealand fishing company.