diff --git a/src/station.cpp b/src/station.cpp
--- a/src/station.cpp
+++ b/src/station.cpp
@@ -75,6 +75,14 @@ Station::~Station()
 		if (a->targetairport == this->index) a->targetairport = INVALID_STATION;
 	}
 
+	Vehicle *v;
+	FOR_ALL_VEHICLES(v) {
+		/* Forget about this station if this station is removed */
+		if (v->last_station_visited == destination && type == OT_GOTO_STATION) {
+			v->last_station_visited = INVALID_STATION;
+		}
+	}
+
 	MarkDirty();
 	InvalidateWindowData(WC_STATION_LIST, this->owner, 0);