Die erste urkundliche Erwähnung des Ortes 973 durch den deutschen Kaiser Otto II gilt als Geburtsstunde des Ortes. Die Bewohner lebten in früheren Zeiten überwiegend vom Fischfang, worauf auch das Wappen des Ortes zurückzuführen ist. Später gewannen Ackerbau und Viehzucht an Bedeutung. Doch das Leben war beschwerlich. Durch die unmittelbare Nähe zum Fluss- zur Elbe- hatten die Bewohner ständig mit Überschwemmungen durch das Hochwasser zu kämpfen. Hinzu kam, dass auch Lostau wie viele andere Dörfer vom Feuer nicht verschont blieb. So wurde beim großen Brand von 1851 der größte Teil des alten Dorfes vernichtet. Aus diesen Gründen siedelten sich die Lostauer immer wieder auf neuen Flächen an. So entstanden im Laufe der Zeit die Ortsteile Altes Dorf, Kleines Dorf und Neu Lostau.

Um das Hochwasser zu bekämpfen, versuchte man seitens der zuständigen Behörden mehr oder weniger erfolgreich den Fluss zu regulieren. Nachdem zum wiederholten Male eine Elbregulierung nicht den gewünschten Erfolg brachte, legten die Lostauer in einer Nacht- und Nebelaktion selbst Hand an. Der Legende nach gruben 1742 ein paar mutige Männer einen etwa 300 Schritt langen und vier bis fünf Fuß breiten Graben und gaben damit der Elbe ein neues Flussbett. In Lostau waren nun die Felder trocken, im Nachbardorf dagegen stieg der Wasserstand. Die Nachbarn beschwerten sich bei keinem Geringeren, als König Friedrich II. Überlieferter Kommentar des großen Friedrichs zur Beschwerde: "Die Lostauer sind Schweinehunde". Und damit blieb der Verlauf der Elbe so bestehen, wie er auch heute noch vorzufinden ist.

Lostau blieb größtenteils verschont von den kriegerischen Auseinandersetzungen um die Befreiung von der französischen Fremdherrschaft. Allerdings hält sich bis heute hartnäckig das Gerücht, dass französische Offiziere einen Schatz in der Lostauer Heide vergraben haben sollen. Gefunden hat den Schatz jedoch bis heute noch keiner.

Besonders ereignisreich für Lostau war das Jahr 1846, in dem die Eisenbahnlinie Magdeburg-Potsdam fertiggestellt wurde. Die Streckenführung ging direkt durch Lostau. Leider entsprach der Bahndamm, durch das öfter auftretende Hochwasser nicht mehr den Sicherheitsstandards der Bahn. Aus diesem Grund verlegte man die Strecke weiter nach Osten und Lostau verlor damit seinen Bahnanschluss.

1902 wurde hier im Ort eine Lungenheilstätte erbaut. Auch heute noch ist die Klinik, die nunmehr zu den Pfeifferschen Stiftungen gehört, ein Krankenhaus zur Behandlung von Lungenkrankheiten. Die Einrichtung war übrigens die Erste, die 1909 mit einem Röntgenapparat ausgestattet wurde.

Lostau war 2002 akut vom Jahrhunderthochwasser bedroht. Alle Bewohner des Alten Dorfes mussten evakuiert werden, da die Gefahr einer Überschwemmung für diesen Ortsteil drohte.

Ein Jahrhundert verging an der Elbe sehr schnell. Bereits im Jahr 2013 war Lostau wieder vom Hochwasser bedroht, diesmal war der Pegel über 70 cm höher als 2002. Von der Straße im Alten Dorf blieben lediglich 20 Meter trocken. Das Wasser war bis in die Kirche vorgedrungen. Der alte Bahndamm, der das Kleine Dorf schützt, drohte komplett überspült zu werden und wurde provisorisch mit Sandsäcken erhöht. Er konnte nur mit sehr vielen Helfern knapp verteidigt werden.