States of matter for elements and pure substances are determined by a combination of pressure and temperature. (When no pressure is specified, we assume 1 atmosphere of pressure, which is the average air pressure found on the Earth's surface.)
Although -39C is commonly referred to as Mercury's "melting point", it is also its freezing point. That is, it's the temperature at which Mercury makes the transition between the liquid state and the solid state. Consequently Mercury can exists as either a liquid, a solid, or a mixture of both phases at -39C. At temperatures below that, it will be a solid.
Similarly, 357C is the temperature at which Mercury can be either a liquid or a gas. At temperatures higher than that is will be found in the gas state.