diff --git a/doc/administration/audit_event_streaming/audit_event_types.md b/doc/administration/audit_event_streaming/audit_event_types.md
index 5c27dabe378649354fab452f2d51de72fd3411da..d3f123a18508e8cff7bab1fe00cce3a8e47b07bf 100644
--- a/doc/administration/audit_event_streaming/audit_event_types.md
+++ b/doc/administration/audit_event_streaming/audit_event_types.md
@@ -246,6 +246,13 @@ audit events to external destinations.
 | [`protected_branch_created`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/92074) | Triggered when a protected branch is created | **{check-circle}** Yes | **{check-circle}** Yes | `source_code_management` | GitLab [15.2](https://gitlab.com/gitlab-org/gitlab/-/issues/363091) |
 | [`protected_branch_removed`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/92074) | Triggered when a protected branch is removed | **{check-circle}** Yes | **{check-circle}** Yes | `source_code_management` | GitLab [15.2](https://gitlab.com/gitlab-org/gitlab/-/issues/363091) |
 | [`protected_branch_updated`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/107530) | Event triggered on the setting for protected branches is update | **{check-circle}** Yes | **{check-circle}** Yes | `source_code_management` | GitLab [15.8](https://gitlab.com/gitlab-org/gitlab/-/issues/369318) |
+| [`protected_environment_approval_rule_added`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484) | This event is triggered when an approval rule is added to a protected environment. | **{check-circle}** Yes | **{check-circle}** Yes | `environment_management` | GitLab [16.5](https://gitlab.com/gitlab-org/gitlab/-/issues/415603) |
+| [`protected_environment_approval_rule_deleted`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484) | This event is triggered when an approval rule is removed from a protected environment. | **{check-circle}** Yes | **{check-circle}** Yes | `environment_management` | GitLab [16.5](https://gitlab.com/gitlab-org/gitlab/-/issues/415603) |
+| [`protected_environment_approval_rule_updated`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484) | This event is triggered when an approval rule of a protected environment is updated. | **{check-circle}** Yes | **{check-circle}** Yes | `environment_management` | GitLab [16.5](https://gitlab.com/gitlab-org/gitlab/-/issues/415603) |
+| [`protected_environment_deploy_access_level_added`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484) | This event is triggered when a deploy access level is added to a protected environment. | **{check-circle}** Yes | **{check-circle}** Yes | `environment_management` | GitLab [16.5](https://gitlab.com/gitlab-org/gitlab/-/issues/415603) |
+| [`protected_environment_deploy_access_level_deleted`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484) | This event is triggered when a deploy access level is removed from a protected environment. | **{check-circle}** Yes | **{check-circle}** Yes | `environment_management` | GitLab [16.5](https://gitlab.com/gitlab-org/gitlab/-/issues/415603) |
+| [`protected_environment_deploy_access_level_updated`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484) | This event is triggered when a deploy access level of a protected environment is updated | **{check-circle}** Yes | **{check-circle}** Yes | `environment_management` | GitLab [16.5](https://gitlab.com/gitlab-org/gitlab/-/issues/415603) |
+| [`protected_environment_updated`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484) | This event is triggered when a protected environment is updated. | **{check-circle}** Yes | **{check-circle}** Yes | `environment_management` | GitLab [16.5](https://gitlab.com/gitlab-org/gitlab/-/issues/415603) |
 | [`registration_created`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/123080) | Event triggered when a user registers for instance access | **{check-circle}** Yes | **{check-circle}** Yes | `compliance_management` | GitLab [16.3](https://gitlab.com/gitlab-org/gitlab/-/issues/374107) |
 | [`release_created`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/111080) | Event triggered when a release is created | **{check-circle}** Yes | **{check-circle}** Yes | `compliance_management` | GitLab [15.9](https://gitlab.com/gitlab-org/gitlab/-/issues/374111) |
 | [`release_deleted_audit_event`](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/111080) | Event triggered when a release is deleted | **{check-circle}** Yes | **{check-circle}** Yes | `compliance_management` | GitLab [15.9](https://gitlab.com/gitlab-org/gitlab/-/issues/374111) |
diff --git a/ee/app/services/protected_environments/update_service.rb b/ee/app/services/protected_environments/update_service.rb
index 690e23da86028a30588681f52ce47204fd7cc13f..ea010f97401aeea877753c8038dd35662a11324c 100644
--- a/ee/app/services/protected_environments/update_service.rb
+++ b/ee/app/services/protected_environments/update_service.rb
@@ -1,8 +1,78 @@
 # frozen_string_literal: true
 module ProtectedEnvironments
   class UpdateService < ProtectedEnvironments::BaseService
+    include ::Audit::Changes
+
+    AUDITABLE_ATTRIBUTES = [:required_approval_count].freeze
+
     def execute(protected_environment)
-      protected_environment.update(sanitized_params)
+      # before updating the `protected_environment`, we need to query upfront
+      # the `deploy_access_levels` and `approval_rules` records that are marked for destruction
+      # since `protected_environment.deploy_access_levels` and `protected_environment.approval_rules`
+      # will no longer include these records after update
+      deploy_access_levels_for_destruction = find_deploy_access_levels_for_destruction(protected_environment)
+      approval_rules_for_destruction = find_approval_rules_for_destruction(protected_environment)
+
+      protected_environment.update(sanitized_params).tap do |is_updated|
+        if is_updated
+          log_audit_events(
+            protected_environment: protected_environment,
+            deleted_deploy_access_levels: deploy_access_levels_for_destruction,
+            deleted_approval_rules: approval_rules_for_destruction
+          )
+        end
+      end
+    end
+
+    private
+
+    def find_deploy_access_levels_for_destruction(protected_environment)
+      return [] unless sanitized_params[:deploy_access_levels_attributes].present?
+
+      ids = sanitized_params[:deploy_access_levels_attributes].filter_map { |dal| dal[:id] if dal[:_destroy] }
+      protected_environment.deploy_access_levels.id_in(ids).to_a
+    end
+
+    def find_approval_rules_for_destruction(protected_environment)
+      return [] unless sanitized_params[:approval_rules_attributes].present?
+
+      ids = sanitized_params[:approval_rules_attributes].filter_map { |ar| ar[:id] if ar[:_destroy] }
+      protected_environment.approval_rules.id_in(ids).to_a
+    end
+
+    def log_audit_events(protected_environment:, deleted_deploy_access_levels:, deleted_approval_rules:)
+      audit_changed_attributes(protected_environment)
+
+      audit_authorization_rule_changes(
+        protected_environment: protected_environment,
+        deleted_deploy_access_levels: deleted_deploy_access_levels,
+        deleted_approval_rules: deleted_approval_rules
+      )
+    end
+
+    def audit_changed_attributes(protected_environment)
+      AUDITABLE_ATTRIBUTES.each do |attr_name|
+        audit_changes(
+          attr_name,
+          entity: container,
+          model: protected_environment,
+          event_type: 'protected_environment_updated'
+        )
+      end
+    end
+
+    def audit_authorization_rule_changes(
+      protected_environment:,
+      deleted_deploy_access_levels:,
+      deleted_approval_rules:
+    )
+      ::Audit::ProtectedEnvironmentAuthorizationRuleChangesAuditor.new(
+        author: current_user,
+        scope: container,
+        protected_environment: protected_environment,
+        deleted_deploy_access_levels: deleted_deploy_access_levels,
+        deleted_approval_rules: deleted_approval_rules
+      ).audit
     end
   end
 end
diff --git a/ee/config/audit_events/types/protected_environment_approval_rule_added.yml b/ee/config/audit_events/types/protected_environment_approval_rule_added.yml
new file mode 100644
index 0000000000000000000000000000000000000000..2ee3e9d79b63e164ce699160d3e48a010358a06e
--- /dev/null
+++ b/ee/config/audit_events/types/protected_environment_approval_rule_added.yml
@@ -0,0 +1,9 @@
+---
+name: protected_environment_approval_rule_added
+description: This event is triggered when an approval rule is added to a protected environment.
+introduced_by_issue: https://gitlab.com/gitlab-org/gitlab/-/issues/415603
+introduced_by_mr: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484
+feature_category: environment_management
+milestone: '16.5'
+saved_to_database: true
+streamed: true
diff --git a/ee/config/audit_events/types/protected_environment_approval_rule_deleted.yml b/ee/config/audit_events/types/protected_environment_approval_rule_deleted.yml
new file mode 100644
index 0000000000000000000000000000000000000000..de43153ffb6c2279f387d585baccc1158c501c9f
--- /dev/null
+++ b/ee/config/audit_events/types/protected_environment_approval_rule_deleted.yml
@@ -0,0 +1,9 @@
+---
+name: protected_environment_approval_rule_deleted
+description: This event is triggered when an approval rule is removed from a protected environment.
+introduced_by_issue: https://gitlab.com/gitlab-org/gitlab/-/issues/415603
+introduced_by_mr: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484
+feature_category: environment_management
+milestone: '16.5'
+saved_to_database: true
+streamed: true
diff --git a/ee/config/audit_events/types/protected_environment_approval_rule_updated.yml b/ee/config/audit_events/types/protected_environment_approval_rule_updated.yml
new file mode 100644
index 0000000000000000000000000000000000000000..5573b98b9a1d1974c5ac66c62bc3d45dc0dcda8e
--- /dev/null
+++ b/ee/config/audit_events/types/protected_environment_approval_rule_updated.yml
@@ -0,0 +1,9 @@
+---
+name: protected_environment_approval_rule_updated
+description: This event is triggered when an approval rule of a protected environment is updated.
+introduced_by_issue: https://gitlab.com/gitlab-org/gitlab/-/issues/415603
+introduced_by_mr: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484
+feature_category: environment_management
+milestone: '16.5'
+saved_to_database: true
+streamed: true
diff --git a/ee/config/audit_events/types/protected_environment_deploy_access_level_added.yml b/ee/config/audit_events/types/protected_environment_deploy_access_level_added.yml
new file mode 100644
index 0000000000000000000000000000000000000000..c6c5290bf9d24d75d50fb9b059c498a8f3039772
--- /dev/null
+++ b/ee/config/audit_events/types/protected_environment_deploy_access_level_added.yml
@@ -0,0 +1,9 @@
+---
+name: protected_environment_deploy_access_level_added
+description: This event is triggered when a deploy access level is added to a protected environment.
+introduced_by_issue: https://gitlab.com/gitlab-org/gitlab/-/issues/415603
+introduced_by_mr: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484
+feature_category: environment_management
+milestone: '16.5'
+saved_to_database: true
+streamed: true
diff --git a/ee/config/audit_events/types/protected_environment_deploy_access_level_deleted.yml b/ee/config/audit_events/types/protected_environment_deploy_access_level_deleted.yml
new file mode 100644
index 0000000000000000000000000000000000000000..0581e9c2db29f3953780426300c3b2cfac853308
--- /dev/null
+++ b/ee/config/audit_events/types/protected_environment_deploy_access_level_deleted.yml
@@ -0,0 +1,9 @@
+---
+name: protected_environment_deploy_access_level_deleted
+description: This event is triggered when a deploy access level is removed from a protected environment.
+introduced_by_issue: https://gitlab.com/gitlab-org/gitlab/-/issues/415603
+introduced_by_mr: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484
+feature_category: environment_management
+milestone: '16.5'
+saved_to_database: true
+streamed: true
diff --git a/ee/config/audit_events/types/protected_environment_deploy_access_level_updated.yml b/ee/config/audit_events/types/protected_environment_deploy_access_level_updated.yml
new file mode 100644
index 0000000000000000000000000000000000000000..79bc38f6abd1731f157e608f2ef98c3d40c80ebf
--- /dev/null
+++ b/ee/config/audit_events/types/protected_environment_deploy_access_level_updated.yml
@@ -0,0 +1,9 @@
+---
+name: protected_environment_deploy_access_level_updated
+description: This event is triggered when a deploy access level of a protected environment is updated
+introduced_by_issue: https://gitlab.com/gitlab-org/gitlab/-/issues/415603
+introduced_by_mr: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484
+feature_category: environment_management
+milestone: '16.5'
+saved_to_database: true
+streamed: true
diff --git a/ee/config/audit_events/types/protected_environment_updated.yml b/ee/config/audit_events/types/protected_environment_updated.yml
new file mode 100644
index 0000000000000000000000000000000000000000..fde6fc1cd6285ea3ed9de1f1f9c6570ecdaff4a0
--- /dev/null
+++ b/ee/config/audit_events/types/protected_environment_updated.yml
@@ -0,0 +1,9 @@
+---
+name: protected_environment_updated
+description: This event is triggered when a protected environment is updated.
+introduced_by_issue: https://gitlab.com/gitlab-org/gitlab/-/issues/415603
+introduced_by_mr: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131484
+feature_category: environment_management
+milestone: '16.5'
+saved_to_database: true
+streamed: true
diff --git a/ee/lib/audit/protected_environment_authorization_rule_changes_auditor.rb b/ee/lib/audit/protected_environment_authorization_rule_changes_auditor.rb
new file mode 100644
index 0000000000000000000000000000000000000000..5eb0ef29297caea80c7f60b685b0544a7fef12a9
--- /dev/null
+++ b/ee/lib/audit/protected_environment_authorization_rule_changes_auditor.rb
@@ -0,0 +1,172 @@
+# frozen_string_literal: true
+
+module Audit
+  class ProtectedEnvironmentAuthorizationRuleChangesAuditor
+    AUTHORIZABLE_ATTRIBUTES = [:access_level, :user_id, :group_id].freeze
+
+    def initialize(author:, scope:, protected_environment:, deleted_deploy_access_levels:, deleted_approval_rules:)
+      @author = author
+      @scope = scope
+      @protected_environment = protected_environment
+      @deleted_deploy_access_levels = deleted_deploy_access_levels
+      @deleted_approval_rules = deleted_approval_rules
+    end
+
+    def audit
+      audit_changed_deploy_access_levels
+      audit_changed_approval_rules
+    end
+
+    private
+
+    attr_reader :author, :scope, :protected_environment, :deleted_deploy_access_levels, :deleted_approval_rules
+
+    def audit_changed_deploy_access_levels
+      audit_deleted_deploy_access_levels
+      audit_created_and_updated_deploy_access_levels
+    end
+
+    def audit_deleted_deploy_access_levels
+      deleted_deploy_access_levels.each do |deploy_access_level|
+        audit_event(
+          event_name: 'protected_environment_deploy_access_level_deleted',
+          message: "Deleted deploy access level #{deploy_access_level.humanize}."
+        )
+      end
+    end
+
+    def audit_created_and_updated_deploy_access_levels
+      protected_environment.deploy_access_levels.each do |deploy_access_level|
+        if deploy_access_level.previously_new_record?
+          audit_event(
+            event_name: 'protected_environment_deploy_access_level_added',
+            message: "Added deploy access level #{deploy_access_level.humanize}."
+          )
+        elsif deploy_access_level_has_changes?(deploy_access_level)
+          audit_event(
+            event_name: 'protected_environment_deploy_access_level_updated',
+            message: updated_deploy_access_level_message(deploy_access_level)
+          )
+        end
+      end
+    end
+
+    def audit_changed_approval_rules
+      audit_deleted_approval_rules
+      audit_created_and_updated_approval_rules
+    end
+
+    def audit_deleted_approval_rules
+      deleted_approval_rules.each do |approval_rule|
+        audit_event(
+          event_name: 'protected_environment_approval_rule_deleted',
+          message: "Deleted approval rule for #{approval_rule.humanize}."
+        )
+      end
+    end
+
+    def audit_created_and_updated_approval_rules
+      protected_environment.approval_rules.each do |approval_rule|
+        if approval_rule.previously_new_record?
+          audit_event(
+            event_name: 'protected_environment_approval_rule_added',
+            message: "Added approval rule for #{approval_rule.humanize} " \
+                     "with required approval count #{approval_rule.required_approvals}."
+          )
+        elsif approval_rule_has_changes?(approval_rule)
+          audit_event(
+            event_name: 'protected_environment_approval_rule_updated',
+            message: updated_approval_rule_message(approval_rule)
+          )
+        end
+      end
+    end
+
+    def deploy_access_level_has_changes?(deploy_access_level)
+      deploy_access_level.previous_changes.keys.any? { |key| AUTHORIZABLE_ATTRIBUTES.include?(key.to_sym) }
+    end
+
+    def updated_deploy_access_level_message(deploy_access_level)
+      changed_access_levels = changed_access_level_details(deploy_access_level)
+      "Changed deploy access level from #{changed_access_levels[:old_access_level]} " \
+        "to #{changed_access_levels[:new_access_level]}."
+    end
+
+    def approval_rule_has_changes?(approval_rule)
+      auditable_attributes = AUTHORIZABLE_ATTRIBUTES + [:required_approvals]
+      approval_rule.previous_changes.keys.any? { |key| auditable_attributes.include?(key.to_sym) }
+    end
+
+    def updated_approval_rule_message(approval_rule)
+      changed_access_levels = changed_access_level_details(approval_rule)
+      changed_approval_counts = approval_rule.previous_changes[:required_approvals]
+
+      if changed_access_levels.present?
+        update_approval_rule_access_level_message(approval_rule, changed_access_levels, changed_approval_counts)
+      else
+        update_approval_rule_approval_count_message(approval_rule, changed_approval_counts)
+      end
+    end
+
+    def update_approval_rule_access_level_message(approval_rule, changed_access_levels, changed_approval_counts)
+      old_access_level_approval_count = changed_approval_counts&.first || approval_rule.required_approvals
+      new_access_level_approval_count = approval_rule.required_approvals
+
+      "Updated approval rule for #{changed_access_levels[:old_access_level]} " \
+        "with required approval count #{old_access_level_approval_count} " \
+        "to #{changed_access_levels[:new_access_level]} " \
+        "with required approval count #{new_access_level_approval_count}."
+    end
+
+    def update_approval_rule_approval_count_message(approval_rule, changed_approval_counts)
+      "Updated approval rule for #{approval_rule.humanize} " \
+        "with required approval count " \
+        "from #{changed_approval_counts.first} " \
+        "to #{changed_approval_counts.last}."
+    end
+
+    def changed_access_level_details(authorizable_object)
+      # The AUTHORIZABLE_ATTRIBUTES (:access_level, :user_id, :group_id) are mutually exclusive
+      # This means that an authorizable_object (deploy_access_level or approval_rule)
+      # can only have one of :access_level, :user_id, or :group_id present
+      # A "change" can mean either of the following:
+      #   - the value of the same attribute is changed, e.g.: user_id=1 to user_id=2
+      #   - the value of one attribute becomes nil, and the value of another attribute is set,
+      #     e.g.: { user_id: 1, access_level: nil } to { user_id: nil, access_level: 40 }
+      changes = authorizable_object.previous_changes.slice(*AUTHORIZABLE_ATTRIBUTES)
+      return unless changes.present?
+
+      # changes are formatted as such: { attr_name: [old_value, new_value] }
+      # the old access level is determined by which attribute has the old_value present
+      # the new access level is determined by which attribute has the new_value present
+      old_access_level = changes.detect { |_, changed_values| changed_values.first.present? }
+      new_access_level = changes.detect { |_, changed_values| changed_values.last.present? }
+
+      {
+        old_access_level: humanize(type: old_access_level[0], value: old_access_level[1].first),
+        new_access_level: humanize(type: new_access_level[0], value: new_access_level[1].last)
+      }
+    end
+
+    def humanize(type:, value:)
+      case type.to_sym
+      when :access_level
+        ::ProtectedEnvironments::DeployAccessLevel::HUMAN_ACCESS_LEVELS[value]
+      when :user_id
+        "user with ID #{value}"
+      when :group_id
+        "group with ID #{value}"
+      end
+    end
+
+    def audit_event(event_name:, message:)
+      ::Gitlab::Audit::Auditor.audit(
+        name: event_name,
+        author: author,
+        scope: scope,
+        target: protected_environment,
+        message: message
+      )
+    end
+  end
+end
diff --git a/ee/spec/factories/protected_environments.rb b/ee/spec/factories/protected_environments.rb
index 92307b0b9bf7ca21fc39303439570dce5d9a2fb1..a2804f15cda58e1cc7efd870aeff94cc063d8681 100644
--- a/ee/spec/factories/protected_environments.rb
+++ b/ee/spec/factories/protected_environments.rb
@@ -7,15 +7,22 @@
     transient do
       authorize_user_to_deploy { nil }
       authorize_group_to_deploy { nil }
+      require_users_to_approve { [] }
     end
 
     after(:build) do |protected_environment, evaluator|
-      if user = evaluator.authorize_user_to_deploy
-        protected_environment.deploy_access_levels.new(user: user)
+      if deploy_user = evaluator.authorize_user_to_deploy
+        protected_environment.deploy_access_levels.new(user: deploy_user)
       end
 
-      if group = evaluator.authorize_group_to_deploy
-        protected_environment.deploy_access_levels.new(group: group)
+      if deploy_group = evaluator.authorize_group_to_deploy
+        protected_environment.deploy_access_levels.new(group: deploy_group)
+      end
+
+      if (approve_users = evaluator.require_users_to_approve).present?
+        approve_users.each do |approve_user|
+          protected_environment.approval_rules.new(user_id: approve_user.id, required_approvals: 1)
+        end
       end
     end
 
@@ -43,6 +50,12 @@
       end
     end
 
+    trait :maintainers_can_approve do
+      after(:build) do |protected_environment|
+        protected_environment.approval_rules.new(access_level: Gitlab::Access::MAINTAINER, required_approvals: 1)
+      end
+    end
+
     trait :production do
       name { 'production' }
     end
diff --git a/ee/spec/lib/audit/protected_environment_authorization_rule_changes_auditor_spec.rb b/ee/spec/lib/audit/protected_environment_authorization_rule_changes_auditor_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..d77c2225746f7bba1208c49b244790cbd492e1f9
--- /dev/null
+++ b/ee/spec/lib/audit/protected_environment_authorization_rule_changes_auditor_spec.rb
@@ -0,0 +1,158 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+
+RSpec.describe Audit::ProtectedEnvironmentAuthorizationRuleChangesAuditor, '#audit', feature_category: :environment_management do
+  let_it_be(:project) { create(:project) }
+  let(:user) { create(:user) }
+  let(:invited_group) { create(:group) }
+  let(:project_user) { project.users.first }
+  let(:admin_user) { create(:user, :admin) }
+
+  let(:protected_environment) do
+    create(
+      :protected_environment,
+      :maintainers_can_deploy,
+      :maintainers_can_approve,
+      authorize_user_to_deploy: admin_user,
+      require_users_to_approve: [admin_user, project_user],
+      name: 'staging',
+      required_approval_count: 1,
+      project: project
+    )
+  end
+
+  let(:deploy_access_levels) { protected_environment.deploy_access_levels }
+  let(:deploy_access_for_delete) { find_authorization_rule(deploy_access_levels, :user_id, admin_user.id) }
+  let(:deploy_access_for_update) do
+    find_authorization_rule(deploy_access_levels, :access_level, Gitlab::Access::MAINTAINER)
+  end
+
+  let(:approval_rules) { protected_environment.approval_rules }
+  let(:approval_rule_for_delete) { find_authorization_rule(approval_rules, :user_id, admin_user.id) }
+  let(:approval_rule_for_update_1) { find_authorization_rule(approval_rules, :user_id, project_user.id) }
+  let(:approval_rule_for_update_2) do
+    find_authorization_rule(approval_rules, :access_level, Gitlab::Access::MAINTAINER)
+  end
+
+  let(:params) do
+    {
+      deploy_access_levels_attributes: [
+        { id: deploy_access_for_delete.id, _destroy: true },
+        { id: deploy_access_for_update.id, access_level: nil, user_id: project_user.id },
+        { access_level: Gitlab::Access::DEVELOPER }
+      ],
+      approval_rules_attributes: [
+        { id: approval_rule_for_delete.id, _destroy: true },
+        {
+          id: approval_rule_for_update_1.id,
+          access_level: nil, user_id: nil,
+          group_id: invited_group.id,
+          required_approvals: 5
+        },
+        { id: approval_rule_for_update_2.id, required_approvals: 4 },
+        { access_level: Gitlab::Access::DEVELOPER, required_approvals: 1 }
+      ]
+    }
+  end
+
+  before do
+    project.project_group_links.create!(
+      group_id: invited_group.id,
+      group_access: Gitlab::Access::DEVELOPER,
+      expires_at: 1.month.from_now
+    )
+
+    allow(::Gitlab::Audit::Auditor).to receive(:audit)
+  end
+
+  subject do
+    protected_environment.update!(params)
+
+    described_class.new(
+      author: user,
+      scope: project,
+      protected_environment: protected_environment,
+      deleted_deploy_access_levels: [deploy_access_for_delete],
+      deleted_approval_rules: [approval_rule_for_delete]
+    ).audit
+  end
+
+  it 'stores and logs the audit events for the changes in deploy_access_levels', :aggregate_failures do
+    subject
+
+    expected_audit_context = {
+      author: user,
+      scope: project,
+      target: protected_environment.reload
+    }
+
+    expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+      expected_audit_context.merge(
+        name: 'protected_environment_deploy_access_level_deleted',
+        message: "Deleted deploy access level #{deploy_access_for_delete.humanize}."
+      )
+    )
+    expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+      expected_audit_context.merge(
+        name: 'protected_environment_deploy_access_level_updated',
+        message: "Changed deploy access level " \
+                 "from #{humanize_access_level(Gitlab::Access::MAINTAINER)} " \
+                 "to user with ID #{project_user.id}."
+      )
+    )
+    expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+      expected_audit_context.merge(
+        name: 'protected_environment_deploy_access_level_added',
+        message: "Added deploy access level #{humanize_access_level(Gitlab::Access::DEVELOPER)}."
+      )
+    )
+  end
+
+  it 'stores and logs the audit events for the changes in approval_rules', :aggregate_failures do
+    subject
+
+    expected_audit_context = {
+      author: user,
+      scope: project,
+      target: protected_environment.reload
+    }
+
+    expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+      expected_audit_context.merge(
+        name: 'protected_environment_approval_rule_deleted',
+        message: "Deleted approval rule for #{approval_rule_for_delete.humanize}."
+      )
+    )
+    expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+      expected_audit_context.merge(
+        name: 'protected_environment_approval_rule_updated',
+        message: "Updated approval rule for user with ID #{project_user.id} " \
+                 "with required approval count 1 " \
+                 "to group with ID #{invited_group.id} with required approval count 5."
+      )
+    )
+    expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+      expected_audit_context.merge(
+        name: 'protected_environment_approval_rule_updated',
+        message: "Updated approval rule for #{humanize_access_level(Gitlab::Access::MAINTAINER)} " \
+                 "with required approval count from 1 to 4."
+      )
+    )
+    expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+      expected_audit_context.merge(
+        name: 'protected_environment_approval_rule_added',
+        message: "Added approval rule for #{humanize_access_level(Gitlab::Access::DEVELOPER)} " \
+                 "with required approval count 1."
+      )
+    )
+  end
+
+  def humanize_access_level(access_level)
+    ::ProtectedEnvironments::DeployAccessLevel::HUMAN_ACCESS_LEVELS[access_level]
+  end
+
+  def find_authorization_rule(authorization_rules, attr_name, attr_value)
+    authorization_rules.detect { |ar| ar.send(attr_name) == attr_value }
+  end
+end
diff --git a/ee/spec/services/protected_environments/update_service_spec.rb b/ee/spec/services/protected_environments/update_service_spec.rb
index 0ce5ba17ed2b1d3b1e1f2c0e8912420e152a55c7..000ea75ec3673bd24a3174ed8b3bbc0850d9ec88 100644
--- a/ee/spec/services/protected_environments/update_service_spec.rb
+++ b/ee/spec/services/protected_environments/update_service_spec.rb
@@ -1,7 +1,7 @@
 # frozen_string_literal: true
 require 'spec_helper'
 
-RSpec.describe ProtectedEnvironments::UpdateService, '#execute' do
+RSpec.describe ProtectedEnvironments::UpdateService, '#execute', feature_category: :environment_management do
   let(:project) { create(:project) }
   let(:user) { create(:user) }
   let(:maintainer_access) { Gitlab::Access::MAINTAINER }
@@ -72,4 +72,206 @@
 
     it_behaves_like 'valid protected environment user'
   end
+
+  describe 'auditing changes' do
+    before do
+      project.project_group_links.create!(
+        group_id: invited_group.id,
+        group_access: Gitlab::Access::DEVELOPER,
+        expires_at: 1.month.from_now
+      )
+
+      allow(::Gitlab::Audit::Auditor).to receive(:audit)
+    end
+
+    let(:admin_user) { create(:user, :admin) }
+
+    let(:invited_group) { create(:group) }
+    let(:project_user) { project.users.first }
+
+    let(:protected_environment) do
+      create(
+        :protected_environment,
+        :maintainers_can_deploy,
+        :maintainers_can_approve,
+        authorize_user_to_deploy: admin_user,
+        require_users_to_approve: [admin_user, project_user],
+        name: 'staging',
+        required_approval_count: 1,
+        project: project
+      )
+    end
+
+    let(:deploy_access_levels) { protected_environment.deploy_access_levels }
+    let(:deploy_access_for_delete) { find_authorization_rule(deploy_access_levels, :user_id, admin_user.id) }
+    let(:deploy_access_for_update) do
+      find_authorization_rule(deploy_access_levels, :access_level, Gitlab::Access::MAINTAINER)
+    end
+
+    let(:approval_rules) { protected_environment.approval_rules }
+    let(:approval_rule_for_delete) { find_authorization_rule(approval_rules, :user_id, admin_user.id) }
+    let(:approval_rule_for_update_1) { find_authorization_rule(approval_rules, :user_id, project_user.id) }
+    let(:approval_rule_for_update_2) do
+      find_authorization_rule(approval_rules, :access_level, Gitlab::Access::MAINTAINER)
+    end
+
+    let(:params) do
+      {
+        required_approval_count: 3,
+        deploy_access_levels_attributes: [
+          { id: deploy_access_for_delete.id, _destroy: true },
+          { id: deploy_access_for_update.id, access_level: nil, user_id: project_user.id },
+          { access_level: Gitlab::Access::DEVELOPER }
+        ],
+        approval_rules_attributes: [
+          { id: approval_rule_for_delete.id, _destroy: true },
+          {
+            id: approval_rule_for_update_1.id,
+            access_level: nil, user_id: nil,
+            group_id: invited_group.id,
+            required_approvals: 5
+          },
+          { id: approval_rule_for_update_2.id, required_approvals: 4 },
+          { access_level: Gitlab::Access::DEVELOPER, required_approvals: 1 }
+        ]
+      }
+    end
+
+    it 'stores and logs the audit event for the protected_environment update' do
+      subject
+
+      expected_audit_context = {
+        name: 'protected_environment_updated',
+        author: user,
+        scope: project,
+        target: protected_environment.reload,
+        message: "Changed required_approval_count from 1 to 3",
+        target_details: nil,
+        additional_details: {
+          change: :required_approval_count,
+          from: 1,
+          to: 3
+        }
+      }
+
+      expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(expected_audit_context)
+    end
+
+    it 'stores and logs the audit events for the changes in deploy_access_levels', :aggregate_failures do
+      subject
+
+      expected_audit_context = {
+        author: user,
+        scope: project,
+        target: protected_environment.reload
+      }
+
+      expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+        expected_audit_context.merge(
+          name: 'protected_environment_deploy_access_level_deleted',
+          message: "Deleted deploy access level #{deploy_access_for_delete.humanize}."
+        )
+      )
+      expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+        expected_audit_context.merge(
+          name: 'protected_environment_deploy_access_level_updated',
+          message: "Changed deploy access level " \
+                   "from #{humanize_access_level(Gitlab::Access::MAINTAINER)} " \
+                   "to user with ID #{project_user.id}."
+        )
+      )
+      expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+        expected_audit_context.merge(
+          name: 'protected_environment_deploy_access_level_added',
+          message: "Added deploy access level #{humanize_access_level(Gitlab::Access::DEVELOPER)}."
+        )
+      )
+    end
+
+    it 'stores and logs the audit events for the changes in approval_rules' do
+      subject
+
+      expected_audit_context = {
+        author: user,
+        scope: project,
+        target: protected_environment.reload
+      }
+
+      expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+        expected_audit_context.merge(
+          name: 'protected_environment_approval_rule_deleted',
+          message: "Deleted approval rule for #{approval_rule_for_delete.humanize}."
+        )
+      )
+      expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+        expected_audit_context.merge(
+          name: 'protected_environment_approval_rule_updated',
+          message: "Updated approval rule for user with ID #{project_user.id} " \
+                   "with required approval count 1 " \
+                   "to group with ID #{invited_group.id} with required approval count 5."
+        )
+      )
+      expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+        expected_audit_context.merge(
+          name: 'protected_environment_approval_rule_updated',
+          message: "Updated approval rule for #{humanize_access_level(Gitlab::Access::MAINTAINER)} " \
+                   "with required approval count from 1 to 4."
+        )
+      )
+      expect(::Gitlab::Audit::Auditor).to have_received(:audit).with(
+        expected_audit_context.merge(
+          name: 'protected_environment_approval_rule_added',
+          message: "Added approval rule for #{humanize_access_level(Gitlab::Access::DEVELOPER)} " \
+                   "with required approval count 1."
+        )
+      )
+    end
+
+    context 'when there are updates to non-auditable attributes only' do
+      let(:params) do
+        {
+          deploy_access_levels_attributes: [
+            { id: deploy_access_for_update.id, group_inheritance_type: 1 }
+          ],
+          approval_rules_attributes: [
+            { id: approval_rule_for_update_2.id, group_inheritance_type: 1 }
+          ]
+        }
+      end
+
+      it 'does not log any audit event' do
+        expect(::Gitlab::Audit::Auditor).not_to receive(:audit).with(
+          name: 'protected_environment_updated'
+        )
+        expect(::Gitlab::Audit::Auditor).not_to receive(:audit).with(
+          name: 'protected_environment_deploy_access_level_added'
+        )
+        expect(::Gitlab::Audit::Auditor).not_to receive(:audit).with(
+          name: 'protected_environment_deploy_access_level_updated'
+        )
+        expect(::Gitlab::Audit::Auditor).not_to receive(:audit).with(
+          name: 'protected_environment_deploy_access_level_deleted'
+        )
+        expect(::Gitlab::Audit::Auditor).not_to receive(:audit).with(
+          name: 'protected_environment_approval_rule_added'
+        )
+        expect(::Gitlab::Audit::Auditor).not_to receive(:audit).with(
+          name: 'protected_environment_approval_rule_updated'
+        )
+        expect(::Gitlab::Audit::Auditor).not_to receive(:audit).with(
+          name: 'protected_environment_approval_rule_deleted'
+        )
+
+        subject
+      end
+    end
+  end
+
+  def humanize_access_level(access_level)
+    ::ProtectedEnvironments::DeployAccessLevel::HUMAN_ACCESS_LEVELS[access_level]
+  end
+
+  def find_authorization_rule(authorization_rules, attr_name, attr_value)
+    authorization_rules.detect { |ar| ar.send(attr_name) == attr_value }
+  end
 end