The floating ice shelf in front of Petermann Glacier, in northwest Greenland, experiences massive bottom melting that removes 80% of its ice before calving into the Arctic Ocean. Detailed surveys of the ice shelf reveal the presence of 1 - 2 km wide, 200 - 400 m deep, sub-ice shelf channels, aligned with the flow direction and spaced by 5 km. We attribute their formation to the bottom melting of ice from warm ocean waters underneath. Drilling at the center of one of channel, only 8 m above sea level, confirms the presence of ice-shelf melt water in the channel. These deep incisions in ice-shelf thickness imply a vulnerability to mechanical break up and climate warming of ice shelves that has not been considered previously.