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. 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. 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.