diff --git a/src/order_cmd.cpp b/src/order_cmd.cpp
--- a/src/order_cmd.cpp
+++ b/src/order_cmd.cpp
@@ -1458,11 +1458,6 @@ void RemoveOrderFromAllVehicles(OrderTyp
 	FOR_ALL_VEHICLES(v) {
 		Order *order;
 
-		/* 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;
-		}
-
 		order = &v->current_order;
 		if ((v->type == VEH_AIRCRAFT && order->IsType(OT_GOTO_DEPOT) ? OT_GOTO_STATION : order->GetType()) == type &&
 				v->current_order.GetDestination() == destination) {
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);