The Martian limb (that is, the observed ‘edge’ of the planet) represents a unique window into the complex atmospheric phenomena occurring there. Clouds of ice crystals (CO2 ice or H2O ice) have been observed numerous times by spacecraft and ground-based telescopes, showing that clouds are typically layered and always confined below an altitude of 100 kilometres; suspended dust has also been detected at altitudes up to 60 kilometres during major dust storms^{1, 2, 3, 4, 5, 6}. Highly concentrated and localized patches of auroral emission controlled by magnetic field anomalies in the crust have been observed at an altitude of 130 kilometres⁷. Here we report the occurrence in March and April 2012 of two bright, extremely high-altitude plumes at the Martian terminator (the day–night boundary) at 200 to 250 kilometres or more above the surface, and thus well into the ionosphere and the exosphere^8, 9. They were spotted at a longitude of about 195° west, a latitude of about −45° (at Terra Cimmeria), extended about 500 to 1,000 kilometres in both the north–south and east–west directions, and lasted for about 10 days. The features exhibited day-to-day variability, and were seen at the morning terminator but not at the evening limb, which indicates rapid evolution in less than 10 hours and a cyclic behaviour. We used photometric measurements to explore two possible scenarios and investigate their nature. For particles reflecting solar radiation, clouds of CO2-ice or H2O-ice particles with an effective radius of 0.1 micrometres are favoured over dust. Alternatively, the plume could arise from auroral emission, of a brightness more than 1,000 times that of the Earth’s aurora, over a region with a strong magnetic anomaly where aurorae have previously been detected⁷. Importantly, both explanations defy our current understanding of Mars’ upper atmosphere.