diff --git a/ee/lib/remote_development/workspace_operations/create/creator_bootstrapper.rb b/ee/lib/remote_development/workspace_operations/create/creator_bootstrapper.rb
index f682f68482f257b6822a794339370653fffb11d4..46bfe152970a8854323bcd6ae99af9a96f19281c 100644
--- a/ee/lib/remote_development/workspace_operations/create/creator_bootstrapper.rb
+++ b/ee/lib/remote_development/workspace_operations/create/creator_bootstrapper.rb
@@ -13,16 +13,14 @@ class CreatorBootstrapper
         def self.bootstrap(context)
           # Skip type checking so we can use fast_spec_helper in the unit test spec
           context => {
-            user: user,
             params: {
               agent: agent
             }
           }
 
-          random_string = SecureRandom.alphanumeric(RANDOM_STRING_LENGTH).downcase
-          # TODO: https://gitlab.com/gitlab-org/gitlab/-/issues/409774
-          #       We can come maybe come up with a better/cooler way to get a unique name, for now this works
-          workspace_name = "workspace-#{agent.id}-#{user.id}-#{random_string}"
+          workspace_name_prefix = "workspace"
+          workspace_name_suffix = generate_unique_workspace_suffix(workspace_name_prefix)
+          workspace_name = "#{workspace_name_prefix}-#{workspace_name_suffix}"
           shared_namespace = agent.unversioned_latest_workspaces_agent_config.shared_namespace
 
           workspace_namespace =
@@ -30,7 +28,7 @@ def self.bootstrap(context)
             case shared_namespace
             when ""
               # Use a unique namespace, with one workspace per namespace
-              "#{NAMESPACE_PREFIX}-#{agent.id}-#{user.id}-#{random_string}"
+              "#{NAMESPACE_PREFIX}-#{workspace_name_suffix}"
             else
               # Use a shared namespace, with multiple workspaces in the same namespace
               shared_namespace
@@ -41,6 +39,32 @@ def self.bootstrap(context)
             workspace_namespace: workspace_namespace
           )
         end
+
+        # @param [String] workspace_name_prefix - This is required to ensure uniqueness
+        # @return [String]
+        def self.generate_unique_workspace_suffix(workspace_name_prefix)
+          max_retries = 30
+
+          max_retries.times do |_|
+            workspace_name_suffix = [
+              FFaker::Food.fruit,
+              FFaker::AnimalUS.common_name,
+              FFaker::Color.name
+            ].map(&:downcase)
+             .map(&:parameterize)
+             .join("-")
+
+            workspace_name = [workspace_name_prefix, workspace_name_suffix].join("-")
+
+            unless workspace_name.length > 64 || RemoteDevelopment::Workspace.by_names(workspace_name).exists?
+              return workspace_name_suffix
+            end
+          end
+
+          raise "Unable to generate unique workspace name after #{max_retries} attempts"
+        end
+
+        private_class_method :generate_unique_workspace_suffix
       end
     end
   end
diff --git a/ee/spec/lib/remote_development/workspace_operations/create/creator_bootstrapper_spec.rb b/ee/spec/lib/remote_development/workspace_operations/create/creator_bootstrapper_spec.rb
index 7466756225a197a29a226b78de8e17ce92fbe451..eb60c8e335089af58ebed7b2ae5094af7d428323 100644
--- a/ee/spec/lib/remote_development/workspace_operations/create/creator_bootstrapper_spec.rb
+++ b/ee/spec/lib/remote_development/workspace_operations/create/creator_bootstrapper_spec.rb
@@ -1,6 +1,7 @@
 # frozen_string_literal: true
 
 require "fast_spec_helper"
+require "ffaker"
 
 # rubocop:disable RSpec/VerifiedDoubleReference -- We're using the quoted version so we can use fast_spec_helper
 RSpec.describe RemoteDevelopment::WorkspaceOperations::Create::CreatorBootstrapper, feature_category: :workspaces do
@@ -10,37 +11,86 @@
     instance_double("RemoteDevelopment::WorkspacesAgentConfig", shared_namespace: shared_namespace)
   end
 
-  let(:user) { instance_double("User", id: 1) }
-
   let(:agent) do
     instance_double("Clusters::Agent", id: 2, unversioned_latest_workspaces_agent_config: workspaces_agent_config)
   end
 
   let(:context) do
     {
-      user: user,
       params: {
         agent: agent
       }
     }
   end
 
-  let(:random_string) { "abcdef" }
-  let(:expected_unique_identifier) { "#{agent.id}-#{user.id}-#{random_string}" }
+  let(:expected_random_name) { 'peach-blue-whale-red' }
 
   subject(:returned_value) do
     described_class.bootstrap(context)
   end
 
-  before do
-    allow(SecureRandom).to receive(:alphanumeric) { random_string }
-  end
-
   describe "workspace_name" do
+    let(:expected_workspace_name) { "workspace-#{expected_random_name}" }
     let(:shared_namespace) { "" }
 
-    it "is set in context" do
-      expect(returned_value.fetch(:workspace_name)).to eq("workspace-#{expected_unique_identifier}")
+    context "when the generated workspace name is unique" do
+      it "is set in context" do
+        allow(FFaker::Food).to receive(:fruit).and_return("Peach")
+        allow(FFaker::AnimalUS).to receive(:common_name).and_return("Blue Whale")
+        allow(FFaker::Color).to receive(:name).and_return("Red")
+
+        stub_const("RemoteDevelopment::Workspace", Class.new)
+        allow(RemoteDevelopment::Workspace)
+          .to receive(:by_names)
+                .with("workspace-peach-blue-whale-red")
+                .and_return(instance_double("ActiveRecord::Relation", exists?: false))
+
+        expect(returned_value.fetch(:workspace_name)).to eq(expected_workspace_name)
+      end
+    end
+
+    context "when the generated workspace name is already taken" do
+      let(:expected_random_name) { 'pear-bald-eagle-green' }
+
+      it "generates another name" do
+        expect(FFaker::Food).to receive(:fruit).and_return("Peach", "Pear")
+        expect(FFaker::AnimalUS).to receive(:common_name).and_return("Blue Whale", "Bald Eagle")
+        expect(FFaker::Color).to receive(:name).and_return("Red", "Green")
+
+        stub_const("RemoteDevelopment::Workspace", Class.new)
+        expect(RemoteDevelopment::Workspace)
+          .to receive(:by_names)
+                .once
+                .with("workspace-peach-blue-whale-red")
+                .and_return(instance_double("ActiveRecord::Relation", exists?: true))
+                .ordered
+        expect(RemoteDevelopment::Workspace)
+          .to receive(:by_names)
+                .once
+                .with("workspace-pear-bald-eagle-green")
+                .and_return(instance_double("ActiveRecord::Relation", exists?: false))
+                .ordered
+        expect(returned_value.fetch(:workspace_name)).to eq(expected_workspace_name)
+      end
+
+      context "when the limit of attempts is reached" do
+        it "raises an error" do
+          expect(FFaker::Food).to receive(:fruit).exactly(30).times.and_return("Peach")
+          expect(FFaker::AnimalUS).to receive(:common_name).exactly(30).times.and_return("Blue Whale")
+          expect(FFaker::Color).to receive(:name).exactly(30).times.and_return("Red")
+
+          stub_const("RemoteDevelopment::Workspace", Class.new)
+          expect(RemoteDevelopment::Workspace)
+            .to receive(:by_names)
+                  .exactly(30)
+                  .times
+                  .with("workspace-peach-blue-whale-red")
+                  .and_return(instance_double("ActiveRecord::Relation", exists?: true))
+
+          expect { returned_value.fetch(:workspace_name) }
+            .to raise_error(/Unable to generate unique workspace name after 30 attempts/)
+        end
+      end
     end
   end
 
@@ -49,8 +99,18 @@
       let(:shared_namespace) { "" }
 
       it "is set in context" do
+        expect(FFaker::Food).to receive(:fruit).and_return("Peach")
+        expect(FFaker::AnimalUS).to receive(:common_name).and_return("Blue Whale")
+        expect(FFaker::Color).to receive(:name).and_return("Red")
+
+        stub_const("RemoteDevelopment::Workspace", Class.new)
+        allow(RemoteDevelopment::Workspace)
+          .to receive(:by_names)
+                .with("workspace-peach-blue-whale-red")
+                .and_return(instance_double("ActiveRecord::Relation", exists?: false))
+
         expect(returned_value.fetch(:workspace_namespace))
-          .to eq("#{create_constants_module::NAMESPACE_PREFIX}-#{agent.id}-#{user.id}-#{random_string}")
+          .to eq("#{create_constants_module::NAMESPACE_PREFIX}-#{expected_random_name}")
       end
     end
 
@@ -58,6 +118,16 @@
       let(:shared_namespace) { "my-shared-namespace" }
 
       it "is set in context" do
+        expect(FFaker::Food).to receive(:fruit).and_return("Peach")
+        expect(FFaker::AnimalUS).to receive(:common_name).and_return("Blue Whale")
+        expect(FFaker::Color).to receive(:name).and_return("Red")
+
+        stub_const("RemoteDevelopment::Workspace", Class.new)
+        allow(RemoteDevelopment::Workspace)
+          .to receive(:by_names)
+                .with("workspace-peach-blue-whale-red")
+                .and_return(instance_double("ActiveRecord::Relation", exists?: false))
+
         expect(returned_value.fetch(:workspace_namespace)).to eq(shared_namespace)
       end
     end
diff --git a/ee/spec/lib/remote_development/workspace_operations/create/main_integration_spec.rb b/ee/spec/lib/remote_development/workspace_operations/create/main_integration_spec.rb
index 76054104727244662fc52e85c49e1f493dc3a7fc..4ee644a2b8a2ffaf92f449512988e3de2b7bc5f3 100644
--- a/ee/spec/lib/remote_development/workspace_operations/create/main_integration_spec.rb
+++ b/ee/spec/lib/remote_development/workspace_operations/create/main_integration_spec.rb
@@ -13,7 +13,7 @@
 
   let(:user) { create(:user) }
   let(:group) { create(:group, name: 'test-group', developers: user) }
-  let(:random_string) { 'abcdef' }
+  let(:random_string) { "miracle-fruit-camel-slategrey" }
   let(:project_ref) { 'master' }
   let(:devfile_path) { '.devfile.yaml' }
   let(:devfile_fixture_name) { 'example.devfile.yaml.erb' }
@@ -130,7 +130,9 @@
   context 'when params are valid' do
     before do
       allow(project.repository).to receive_message_chain(:blob_at_branch, :data) { devfile_yaml }
-      allow(SecureRandom).to receive(:alphanumeric) { random_string }
+      allow(FFaker::Food).to receive(:fruit).and_return("Miracle Fruit")
+      allow(FFaker::AnimalUS).to receive(:common_name).and_return("Camel")
+      allow(FFaker::Color).to receive(:name).and_return("Slategrey")
     end
 
     context 'when devfile is valid' do
@@ -157,9 +159,9 @@
         expect(workspace.desired_state_updated_at).to eq(Time.current)
         expect(workspace.actual_state).to eq(states_module::CREATION_REQUESTED)
         expect(workspace.actual_state_updated_at).to eq(Time.current)
-        expect(workspace.name).to eq("workspace-#{agent.id}-#{user.id}-#{random_string}")
+        expect(workspace.name).to eq("workspace-#{random_string}")
         expect(workspace.namespace)
-          .to eq("#{create_constants_module::NAMESPACE_PREFIX}-#{agent.id}-#{user.id}-#{random_string}")
+          .to eq("#{create_constants_module::NAMESPACE_PREFIX}-#{random_string}")
         expect(workspace.workspaces_agent_config_version).to eq(expected_workspaces_agent_config_version)
         expect(workspace.url).to eq(URI::HTTPS.build({
           host: "#{create_constants_module::WORKSPACE_EDITOR_PORT}-#{workspace.name}." \
@@ -188,7 +190,6 @@
 
         expect(workspace.workspace_agentk_state).to be_present
         expect(workspace.workspace_agentk_state.desired_config).to be_an(Array)
-        pp workspace.workspace_agentk_state.desired_config
       end
 
       it_behaves_like 'tracks successful workspace creation event'
diff --git a/ee/spec/requests/remote_development/integration_spec.rb b/ee/spec/requests/remote_development/integration_spec.rb
index a8665b2c1dcbfedaefa57f3deafd723e2f62cb49..fcd6837cdb3308c33824a2fb1396c12249380530 100644
--- a/ee/spec/requests/remote_development/integration_spec.rb
+++ b/ee/spec/requests/remote_development/integration_spec.rb
@@ -159,7 +159,7 @@ def expected_internal_variables(random_string:, user:)
       { key: "GL_VSCODE_EXTENSION_MARKETPLACE_ITEM_URL", type: :environment, value: "https://open-vsx.org/vscode/item" },
       { key: "GL_VSCODE_EXTENSION_MARKETPLACE_RESOURCE_URL_TEMPLATE", type: :environment, value: "https://open-vsx.org/vscode/unpkg/{publisher}/{name}/{versionRaw}/{path}" },
       { key: "GL_VSCODE_EXTENSION_MARKETPLACE_SERVICE_URL", type: :environment, value: "https://open-vsx.org/vscode/gallery" },
-      { key: "GL_WORKSPACE_DOMAIN_TEMPLATE", type: :environment, value: "${PORT}-workspace-#{agent.id}-#{user.id}-#{random_string}.#{dns_zone}" },
+      { key: "GL_WORKSPACE_DOMAIN_TEMPLATE", type: :environment, value: "${PORT}-workspace-#{random_string}.#{dns_zone}" },
       { key: "GITLAB_WORKFLOW_INSTANCE_URL", type: :environment, value: Gitlab::Routing.url_helpers.root_url },
       { key: "GITLAB_WORKFLOW_TOKEN_FILE", type: :environment, value: token_file_path }
     ]
@@ -265,11 +265,15 @@ def do_create_org_mapping
   end
 
   # rubocop:disable Metrics/AbcSize -- We want this to stay a single method
-  # @param [String] random_string
+  # @param [Array<String>] random_string_array
   # @param [User] user
   # @return [RemoteDevelopment::Workspace]
-  def do_create_workspace(random_string:, user:)
-    allow(SecureRandom).to receive(:alphanumeric) { random_string }
+  def do_create_workspace(random_string_array:, user:)
+    allow(FFaker::Food).to receive(:fruit).and_return(random_string_array[0])
+    allow(FFaker::AnimalUS).to receive(:common_name).and_return(random_string_array[1])
+    allow(FFaker::Color).to receive(:name).and_return(random_string_array[2])
+
+    random_string = random_string_array.join("-").parameterize.downcase
 
     # FETCH THE AGENT CONFIG VIA THE GRAPHQL API, SO WE CAN USE ITS VALUES WHEN CREATING WORKSPACE
     cluster_agent_gid = "gid://gitlab/Clusters::Agent/#{agent.id}"
@@ -291,9 +295,9 @@ def do_create_workspace(random_string:, user:)
     expect(workspace.agent).to eq(agent)
     # noinspection RubyResolve
     expect(workspace.desired_state_updated_at).to eq(Time.current)
-    expect(workspace.name).to eq("workspace-#{agent.id}-#{user.id}-#{random_string}")
+    expect(workspace.name).to eq("workspace-#{random_string}")
     namespace_prefix = create_constants_module::NAMESPACE_PREFIX
-    expect(workspace.namespace).to eq("#{namespace_prefix}-#{agent.id}-#{user.id}-#{random_string}")
+    expect(workspace.namespace).to eq("#{namespace_prefix}-#{random_string}")
     expect(workspace.url).to eq(URI::HTTPS.build({
       host: "#{create_constants_module::WORKSPACE_EDITOR_PORT}-#{workspace.name}.#{dns_zone}",
       path: "/",
@@ -455,7 +459,7 @@ def do_reconcile_post(params:, agent_token:)
       do_create_workspaces_agent_config
 
       # CREATE WORKSPACE VIA GRAPHQL API
-      workspace = do_create_workspace(random_string: "abcdef", user: user)
+      workspace = do_create_workspace(random_string_array: %w[Date Butterfly Darkturquoise], user: user)
 
       additional_args_for_expected_config_to_apply =
         build_additional_args_for_expected_config_to_apply_yaml_stream(
@@ -595,7 +599,7 @@ def do_reconcile_post(params:, agent_token:)
       do_create_org_mapping
 
       # CREATE A NEW WORKSPACE WITH THE ORGANIZATION MAPPING WITH MINIMUM USER PRIVILEGES
-      do_create_workspace(random_string: "ghijkl", user: organization_user)
+      do_create_workspace(random_string_array: ["Peach", "Blue Whale", "Red"], user: organization_user)
     end
   end