Middleton was appointed on 5 March 1741 to the command of the Royal Navy's bomb vessel, HMS Furnace, which was refitted at Deptford Dockyard and re-rigged as a three-masted ship. In May 1741 he left England in the Furnace, accompanied by a smaller vessel, the purchased HMS Discovery under the command of Commander William Moor, and sailed to Hudson Bay in search of a Northwest Passage. He spent the winter at Churchill, Manitoba. He then proceeded north into Roes Welcome Sound and discovered Wager Inlet where he was iced in for three weeks. At the head of the sound he was blocked by ice and named the place Repulse Bay. He returned to England in 1742, where he was presented with the Copley Medal by the Royal Society to whom he presented a paper on "The extraordinary degrees and surprising effects of Cold in Hudson's Bay".