The genus is characterised by the presence of pseudocyphellae (tiny pores that allow for gas exchange), usually on warts or on the tips of isidia, a non-pored epicortex and a medulla containing depsidones or lacking secondary metabolites.

Melanohalea was circumscribed in 2004 as a segregate of the morphologically similar genus Melanelia, which was created in 1978 for certain brown Parmelia species.

The methods used to estimate the evolutionary history of Melanohalea suggest that its diversification primarily occurred during the Miocene and Pliocene epochs.

Melanohalea species predominantly inhabit bark and wood in the Holarctic, with only a few extending into the Southern Hemisphere and rare occurrences on rocks.

Notably, Melanohalea peruviana in the Peruvian Andes and M. mexicana in Mexico represent the genus's limited tropical distribution.

The distribution of these lichens, which are sensitive indicators of climate and pollution effects, is largely determined by current ecological and geographical factors.

Melanohalea was circumscribed in 2004 by the lichenologists Oscar Blanco, Ana Crespo, Pradeep Divakar, Theodore Esslinger, David L. Hawksworth and H. Thorsten Lumbsch.

[1] The "brown parmelioids" refers to Parmelia species lacking atranorin or usnic acid in the cortex, with a dark to medium-brown thallus colour.

[7] The genus name combines Melanelia with the name of the lichenologist Mason Hale, who, according to the authors, "provided the foundations for subsequent contributions to our knowledge of this family".

[9] The lobes comprising the thallus are flat to concave with rounded tips, lack cilia, and measure 0.5–7 mm wide.

The upper surface of the thallus is olive-green to dark brown, ranging in texture from smooth to wrinkled, and lacks spots or stains.

Pleurosticta, although similar to Melanohalea, is characterised by wider lobes, a network of epicortical pores, and a pigment that turns violet upon reacting with both potassium hydroxide (K) and nitric acid (N).

[9] Melanohalea peruviana is the only species in the genus that has been reported from tropical South America, although it is poorly known – a single collection from an altitude of 4,400 feet (1,300 m) in the Peruvian Andes.

[17] Similarly, a study of the effect of air pollution surrounding the Mongolian capital Ulan Bator showed widespread damage to a variety of lichens (where the thallus was bleached, deformed, or reduced in size), including Melanohalea septentrionalis.

Otte and colleagues suggested in a 2005 study that distribution patterns in Melanohalea are largely determined by contemporary ecogeographical factors, and most species have reached their biogeographical limits in the Northern Hemisphere.

Because of its broad geographic distribution, breadth of ecological niches, and large, stable population size, it has been assessed as a least-concern species.

In 2016, Leavitt and colleagues used genetic analyses to help identify six previously undescribed morphologically cryptic species in Melanohalea.