diff --git a/aircraft_cmd.c b/aircraft_cmd.c
--- a/aircraft_cmd.c
+++ b/aircraft_cmd.c
@@ -399,6 +399,7 @@ int32 CmdBuildAircraft(TileIndex tile, u
 		}
 		GetPlayer(_current_player)->num_engines[p1]++;
 
+		InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 		InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
 		RebuildVehicleLists();
 		InvalidateWindow(WC_COMPANY, v->owner);
@@ -1432,6 +1433,7 @@ static void AircraftLeaveHangar(Vehicle 
 
 	VehicleServiceInDepot(v);
 	SetAircraftPosition(v, v->x_pos, v->y_pos, v->z_pos);
+	InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 	InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
 	InvalidateWindowClasses(WC_AIRCRAFT_LIST);
 }
diff --git a/depot_gui.c b/depot_gui.c
--- a/depot_gui.c
+++ b/depot_gui.c
@@ -618,18 +618,43 @@ static void DepotWndProc(Window *w, Wind
 {
 	switch (e->event) {
 		case WE_CREATE:
-			WP(w, depot_d).vehicle_list = NULL;
-			WP(w, depot_d).wagon_list   = NULL;
-			WP(w, depot_d).engine_count = 0;
-			WP(w, depot_d).wagon_count  = 0;
+			WP(w, depot_d).vehicle_list  = NULL;
+			WP(w, depot_d).wagon_list    = NULL;
+			WP(w, depot_d).engine_count  = 0;
+			WP(w, depot_d).wagon_count   = 0;
+			WP(w, depot_d).generate_list = true;
+			break;
+
+		case WE_INVALIDATE_DATA:
+			WP(w, depot_d).generate_list = true;
 			break;
 
 		case WE_PAINT:
-			/* Generate the vehicle list
-			 * It's ok to use the wagon pointers for non-trains as they will be ignored */
-			BuildDepotVehicleList(WP(w, depot_d).type, w->window_number,
-				&WP(w, depot_d).vehicle_list, &WP(w, depot_d).engine_list_length, &WP(w, depot_d).engine_count,
-			    &WP(w, depot_d).wagon_list,   &WP(w, depot_d).wagon_list_length,  &WP(w, depot_d).wagon_count);
+			if (WP(w, depot_d).generate_list) {
+				/* Generate the vehicle list
+				 * It's ok to use the wagon pointers for non-trains as they will be ignored */
+				BuildDepotVehicleList(WP(w, depot_d).type, w->window_number,
+					&WP(w, depot_d).vehicle_list, &WP(w, depot_d).engine_list_length, &WP(w, depot_d).engine_count,
+					&WP(w, depot_d).wagon_list,   &WP(w, depot_d).wagon_list_length,  &WP(w, depot_d).wagon_count);
+				WP(w, depot_d).generate_list = false;
+#ifndef NDEBUG
+			} else {
+				/* Here we got a piece of code, that only checks if we got a different number of vehicles in the depot list and the number of vehicles actually being in the depot.
+				 * IF they aren't the same, then WE_INVALIDATE_DATA should have been called somewhere, but it wasn't and we got a bug
+				 * Since this is a time consuming check and not nice to memory fragmentation, it may not stay for long, but it's a good way to check this
+				 * We can turn it on/off by switching between #ifndef NDEBUG and #if 0 */
+				Vehicle **engines = NULL, **wagons = NULL;
+				uint16 engine_count = 0, engine_length = 0;
+				uint16 wagon_count  = 0, wagon_length  = 0;
+				BuildDepotVehicleList(WP(w, depot_d).type, w->window_number, &engines, &engine_length, &engine_count,
+									  &wagons,  &wagon_length,  &wagon_count);
+
+				assert(engine_count == WP(w, depot_d).engine_count);
+				assert(wagon_count == WP(w, depot_d).wagon_count);
+				free((void*)engines);
+				free((void*)wagons);
+#endif
+			}
 			DrawDepotWindow(w);
 			break;
 
diff --git a/rail_cmd.c b/rail_cmd.c
--- a/rail_cmd.c
+++ b/rail_cmd.c
@@ -2005,6 +2005,7 @@ static uint32 VehicleEnter_Track(Vehicle
 			v->u.rail.track = 0x80,
 			v->vehstatus |= VS_HIDDEN; /* hide it */
 			v->direction = ReverseDir(v->direction);
+			InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 			if (v->next == NULL)
 				VehicleEnterDepot(v);
 			v->tile = tile;
diff --git a/roadveh_cmd.c b/roadveh_cmd.c
--- a/roadveh_cmd.c
+++ b/roadveh_cmd.c
@@ -194,6 +194,7 @@ int32 CmdBuildRoadVeh(TileIndex tile, ui
 		VehiclePositionChanged(v);
 		GetPlayer(_current_player)->num_engines[p1]++;
 
+		InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 		InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
 		RebuildVehicleLists();
 		InvalidateWindow(WC_COMPANY, v->owner);
@@ -1305,6 +1306,7 @@ static void RoadVehController(Vehicle *v
 		UpdateRoadVehDeltaXY(v);
 		SetRoadVehPosition(v,x,y);
 
+		InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 		InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
 		return;
 	}
diff --git a/ship_cmd.c b/ship_cmd.c
--- a/ship_cmd.c
+++ b/ship_cmd.c
@@ -358,6 +358,7 @@ static void CheckShipLeaveDepot(Vehicle 
 
 	PlayShipSound(v);
 	VehicleServiceInDepot(v);
+	InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 	InvalidateWindowClasses(WC_SHIPS_LIST);
 }
 
@@ -882,6 +883,7 @@ int32 CmdBuildShip(TileIndex tile, uint3
 		VehiclePositionChanged(v);
 		GetPlayer(_current_player)->num_engines[p1]++;
 
+		InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 		InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
 		RebuildVehicleLists();
 		InvalidateWindow(WC_COMPANY, v->owner);
diff --git a/train_cmd.c b/train_cmd.c
--- a/train_cmd.c
+++ b/train_cmd.c
@@ -615,6 +615,7 @@ static int32 CmdBuildRailWagon(EngineID 
 				u->next = v;
 			} else {
 				SetFreeWagon(v);
+				InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 			}
 
 			v->cargo_type = rvi->cargo_type;
@@ -818,6 +819,7 @@ int32 CmdBuildRailVehicle(TileIndex tile
 			}
 
 			GetPlayer(_current_player)->num_engines[p1]++;
+			InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 			InvalidateWindow(WC_VEHICLE_DEPOT, tile);
 			RebuildVehicleLists();
 			InvalidateWindow(WC_COMPANY, v->owner);
@@ -1122,6 +1124,7 @@ int32 CmdMoveRailVehicle(TileIndex tile,
 				while (GetNextVehicle(v) != src) v = GetNextVehicle(v);
 				GetLastEnginePart(v)->next = NULL;
 			} else {
+				InvalidateWindowData(WC_VEHICLE_DEPOT, src_head->tile); // We removed a line
 				src_head = NULL;
 			}
 		} else {
@@ -1133,6 +1136,9 @@ int32 CmdMoveRailVehicle(TileIndex tile,
 		}
 
 		if (dst == NULL) {
+			/* We make a new line in the depot, so we know already that we invalidate the window data */
+			InvalidateWindowData(WC_VEHICLE_DEPOT, src_head->tile);
+
 			// move the train to an empty line. for locomotives, we set the type to TS_Front. for wagons, 4.
 			if (IsTrainEngine(src)) {
 				if (!IsFrontEngine(src)) {
@@ -1152,9 +1158,12 @@ int32 CmdMoveRailVehicle(TileIndex tile,
 				DeleteVehicleOrders(src);
 			}
 
-			ClearFrontEngine(src);
-			ClearFreeWagon(src);
-			src->unitnumber = 0; // doesn't occupy a unitnumber anymore.
+			if (IsFrontEngine(src) || IsFreeWagon(src)) {
+				InvalidateWindowData(WC_VEHICLE_DEPOT, src->tile);
+				ClearFrontEngine(src);
+				ClearFreeWagon(src);
+				src->unitnumber = 0; // doesn't occupy a unitnumber anymore.
+			}
 
 			// link in the wagon(s) in the chain.
 			{
@@ -1640,8 +1649,10 @@ static void ReverseTrainDirection(Vehicl
 	int l = 0, r = -1;
 	Vehicle *u;
 
-	if (IsTileDepotType(v->tile, TRANSPORT_RAIL))
+	if (IsTileDepotType(v->tile, TRANSPORT_RAIL)) {
+		InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 		InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
+	}
 
 	/* Check if we were approaching a rail/road-crossing */
 	{
@@ -1672,8 +1683,10 @@ static void ReverseTrainDirection(Vehicl
 
 	AdvanceWagons(v, false);
 
-	if (IsTileDepotType(v->tile, TRANSPORT_RAIL))
+	if (IsTileDepotType(v->tile, TRANSPORT_RAIL)) {
+		InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 		InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
+	}
 
 	CLRBIT(v->u.rail.flags, VRF_REVERSING);
 }
@@ -2166,6 +2179,7 @@ static bool CheckTrainStayInDepot(Vehicl
 	VehiclePositionChanged(v);
 	UpdateSignalsOnSegment(v->tile, DirToDiagDir(v->direction));
 	UpdateTrainAcceleration(v);
+	InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 	InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
 
 	return false;
diff --git a/vehicle.c b/vehicle.c
--- a/vehicle.c
+++ b/vehicle.c
@@ -566,6 +566,10 @@ void DestroyVehicle(Vehicle *v)
 	DeleteName(v->string_id);
 	if (v->type == VEH_Road) ClearSlot(v);
 
+	if (v->type != VEH_Train || (v->type == VEH_Train && (IsFrontEngine(v) || IsFreeWagon(v)))) {
+		InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
+	}
+
 	UpdateVehiclePosHash(v, INVALID_COORD, 0);
 	v->next_hash = INVALID_VEHICLE;
 	if (v->orders != NULL) DeleteVehicleOrders(v);
@@ -2476,6 +2480,11 @@ void VehicleEnterDepot(Vehicle *v)
 		default: NOT_REACHED();
 	}
 
+	if (v->type != VEH_Train) {
+		/* Trains update the vehicle list when the first unit enters the depot and calls VehicleEnterDepot() when the last unit enters.
+		 * We only increase the number of vehicles when the first one enters, so we will not need to search for more vehicles in the depot */
+		InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
+	}
 	InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
 
 	v->vehstatus |= VS_HIDDEN;
diff --git a/window.c b/window.c
--- a/window.c
+++ b/window.c
@@ -1563,6 +1563,14 @@ void InvalidateWindowClasses(WindowClass
 	}
 }
 
+void InvalidateWindowData(WindowClass cls, WindowNumber number)
+{
+	Window *w;
+
+	for (w = _windows; w != _last_window; w++) {
+		if (w->window_class == cls && w->window_number == number) CallWindowEventNP(w, WE_INVALIDATE_DATA);
+	}
+}
 
 void CallWindowTickEvent(void)
 {
diff --git a/window.h b/window.h
--- a/window.h
+++ b/window.h
@@ -99,6 +99,7 @@ enum WindowEventCodes {
 	WE_MESSAGE             = 23,
 	WE_SCROLL              = 24,
 	WE_MOUSEWHEEL          = 25,
+	WE_INVALIDATE_DATA     = 26,
 };
 
 struct WindowEvent {
@@ -397,6 +398,7 @@ assert_compile(WINDOW_CUSTOM_SIZE >= siz
 typedef struct {
 	VehicleID sel;
 	byte type;
+	bool generate_list;
 	uint16 engine_list_length;
 	uint16 wagon_list_length;
 	uint16 engine_count;
@@ -748,6 +750,7 @@ int GetMenuItemIndex(const Window *w, in
 void InputLoop(void);
 void UpdateWindows(void);
 void InvalidateWidget(const Window *w, byte widget_index);
+void InvalidateWindowData(WindowClass cls, WindowNumber number);
 void RaiseWindowButtons(Window *w);
 void RelocateAllWindows(int neww, int newh);
 int PositionMainToolbar(Window *w);