diff --git a/src/company_cmd.cpp b/src/company_cmd.cpp
--- a/src/company_cmd.cpp
+++ b/src/company_cmd.cpp
@@ -888,6 +888,11 @@ CommandCost CmdCompanyCtrl(DoCommandFlag
 				break;
 			}
 
+			/* Send new companies, before potentially setting the password. Otherwise,
+			 * the password update could be sent when the company is not yet known. */
+			NetworkAdminCompanyNew(c);
+			NetworkServerNewCompany(c, ci);
+
 			/* This is the client (or non-dedicated server) who wants a new company */
 			if (client_id == _network_own_client_id) {
 				assert(_local_company == COMPANY_SPECTATOR);
@@ -906,8 +911,6 @@ CommandCost CmdCompanyCtrl(DoCommandFlag
 
 				MarkWholeScreenDirty();
 			}
-
-			NetworkServerNewCompany(c, ci);
 			break;
 		}
 
@@ -923,7 +926,10 @@ CommandCost CmdCompanyCtrl(DoCommandFlag
 			assert(company_id == INVALID_COMPANY || !Company::IsValidID(company_id));
 
 			Company *c = DoStartupNewCompany(true, company_id);
-			if (c != nullptr) NetworkServerNewCompany(c, nullptr);
+			if (c != nullptr) {
+				NetworkAdminCompanyNew(c);
+				NetworkServerNewCompany(c, nullptr);
+			}
 			break;
 		}