diff --git a/src/company_cmd.cpp b/src/company_cmd.cpp
--- a/src/company_cmd.cpp
+++ b/src/company_cmd.cpp
@@ -906,8 +906,6 @@ CommandCost CmdCompanyCtrl(TileIndex til
 			delete c;
 			AI::BroadcastNewEvent(new AIEventCompanyBankrupt(c_index));
 			CompanyAdminBankrupt(c_index);
-			BuildOwnerLegend();
-			InvalidateWindowData(WC_SMALLMAP, 0, 1);
 			break;
 		}
 
diff --git a/src/misc.cpp b/src/misc.cpp
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -25,7 +25,6 @@
 #include "tilehighlight_func.h"
 #include "network/network_func.h"
 #include "window_func.h"
-#include "smallmap_gui.h"
 
 
 extern TileIndex _cur_tileloop_tile;
@@ -122,9 +121,6 @@ void InitializeGame(uint size_x, uint si
 
 	InitializeEconomy();
 
-	/* Rebuild the smallmap owner legend. */
-	BuildOwnerLegend();
-
 	ResetObjectToPlace();
 
 	GamelogReset();
diff --git a/src/smallmap_gui.cpp b/src/smallmap_gui.cpp
--- a/src/smallmap_gui.cpp
+++ b/src/smallmap_gui.cpp
@@ -65,6 +65,9 @@ static const int NUM_NO_COMPANY_ENTRIES 
 /** Macro for non-company owned property entry of LegendAndColour */
 #define MO(a, b) {a, b, {INVALID_COMPANY}, true, false, false}
 
+/** Macro used for forcing a rebuild of the owner legend the first time it is used. */
+#define MOEND() {0, 0, {OWNER_NONE}, true, true, false}
+
 /** Macro for end of list marker in arrays of LegendAndColour */
 #define MKEND() {0, STR_NULL, {INVALID_INDUSTRYTYPE}, true, true, false}
 
@@ -150,13 +153,15 @@ static LegendAndColour _legend_land_owne
 	MO(0x00, STR_SMALLMAP_LEGENDA_NO_OWNER), // This colour will vary depending on settings.
 	MO(0xB4, STR_SMALLMAP_LEGENDA_TOWNS),
 	MO(0x20, STR_SMALLMAP_LEGENDA_INDUSTRIES),
-	/* The legend will be terminated after adding the companies. */
+	/* The legend will be terminated the first time it is used. */
+	MOEND(),
 };
 
 #undef MK
 #undef MC
 #undef MS
 #undef MO
+#undef MOEND
 #undef MKEND
 
 /**
@@ -1107,6 +1112,12 @@ public:
 					str = STR_SMALLMAP_INDUSTRY;
 				} else if (i == SMT_OWNER) {
 					if (tbl->u.company != INVALID_COMPANY) {
+						if (!Company::IsValidID(tbl->u.company)) {
+							/* Rebuild the owner legend. */
+							BuildOwnerLegend();
+							this->OnInit();
+							return;
+						}
 						/* Non-fixed legend entries for the owner view. */
 						SetDParam(0, tbl->u.company);
 						str = STR_SMALLMAP_COMPANY;
@@ -1132,6 +1143,22 @@ public:
 		this->column_width = min_width + LEGEND_BLOB_WIDTH + WD_FRAMERECT_LEFT + WD_FRAMERECT_RIGHT;
 	}
 
+	virtual void OnPaint()
+	{
+		if (this->map_type == SMT_OWNER) {
+			for (const LegendAndColour *tbl = _legend_table[this->map_type]; !tbl->end; ++tbl) {
+				if (tbl->u.company != INVALID_COMPANY && !Company::IsValidID(tbl->u.company)) {
+					/* Rebuild the owner legend. */
+					BuildOwnerLegend();
+					this->InvalidateData(1);
+					break;
+				}
+			}
+		}
+
+		this->DrawWidgets();
+	}
+
 	virtual void DrawWidget(const Rect &r, int widget) const
 	{
 		switch (widget) {