diff --git a/lib/gitlab/ci/config/matrix_interpolator.rb b/lib/gitlab/ci/config/matrix_interpolator.rb
new file mode 100644
index 0000000000000000000000000000000000000000..78d624d9b17909d76cf8f42ee518ab0c2b2874ca
--- /dev/null
+++ b/lib/gitlab/ci/config/matrix_interpolator.rb
@@ -0,0 +1,34 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Ci
+    class Config
+      class MatrixInterpolator
+        def initialize(matrix_variables)
+          @matrix_variables = matrix_variables || {}
+        end
+
+        def interpolate_needs_config(needs_config)
+          interpolate_value(needs_config)
+        end
+
+        private
+
+        def interpolate_value(value)
+          case value
+          when String
+            value.gsub(/\$\[\[\s*matrix\.(\w+)\s*\]\]/) do
+              @matrix_variables[Regexp.last_match(1)]
+            end
+          when Hash
+            value.transform_values { |v| interpolate_value(v) }
+          when Array
+            value.map { |v| interpolate_value(v) }
+          else
+            value
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/ci/config/normalizer.rb b/lib/gitlab/ci/config/normalizer.rb
index a5b692b26d69ced9ef57538300a5c1d699f8dfc3..c0f1b548905bbc07647f3cb3e5727105d0f4bcec 100644
--- a/lib/gitlab/ci/config/normalizer.rb
+++ b/lib/gitlab/ci/config/normalizer.rb
@@ -69,8 +69,14 @@ def expand_parallelize_jobs
           @jobs_config.each_with_object({}) do |(job_name, config), hash|
             if parallelized_jobs.key?(job_name)
               parallelized_jobs[job_name].each do |job|
-                hash[job.name.to_sym] =
-                  yield(job.name, config.deep_merge(job.attributes))
+                merged_config = config.deep_merge(job.attributes)
+
+                if job.attributes[:job_variables] && merged_config[:needs]
+                  interpolator = MatrixInterpolator.new(job.attributes[:job_variables])
+                  merged_config[:needs] = interpolator.interpolate_needs_config(merged_config[:needs])
+                end
+
+                hash[job.name.to_sym] = yield(job.name, merged_config)
               end
             else
               hash[job_name] = yield(job_name, config)
diff --git a/spec/services/ci/create_pipeline_service/matrix_spec.rb b/spec/services/ci/create_pipeline_service/matrix_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..b0d1d9561d86218e92ffb313fd2b1f3194de1385
--- /dev/null
+++ b/spec/services/ci/create_pipeline_service/matrix_spec.rb
@@ -0,0 +1,74 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+
+RSpec.describe Ci::CreatePipelineService, '#execute', feature_category: :pipeline_composition do
+  let_it_be(:project) { create(:project, :repository) }
+  let_it_be(:user) { project.first_owner }
+
+  subject(:service) { described_class.new(project, user, { ref: project.default_branch }).execute(:push) }
+
+  describe 'matrix variable interpolation in needs:parallel:matrix' do
+    let(:config) do
+      <<~YAML
+        .parallel-strat:
+          parallel:
+            matrix:
+              - TARGET: ["linux", "windows"]
+
+        build-job:
+          script: echo "Building for $TARGET"
+          parallel: !reference [.parallel-strat, parallel]
+
+        test-job:
+          script: echo "Testing for $TARGET"
+          parallel: !reference [.parallel-strat, parallel]
+          needs:
+            - job: build-job
+              parallel:
+                matrix:
+                  - TARGET: $[[ matrix.TARGET ]]
+      YAML
+    end
+
+    before do
+      stub_ci_pipeline_yaml_file(config)
+    end
+
+    it 'creates pipeline with correct job dependencies' do
+      pipeline = service.payload
+
+      expect(pipeline).to be_persisted
+      expect(pipeline.builds.count).to eq(4)
+
+      # Check build jobs were created
+      build_jobs = pipeline.builds.where("name LIKE 'build-job:%'")
+      expect(build_jobs.count).to eq(2)
+      expect(build_jobs.pluck(:name)).to match_array([
+        'build-job: [linux]',
+        'build-job: [windows]'
+      ])
+
+      # Check test jobs were created
+      test_jobs = pipeline.builds.where("name LIKE 'test-job:%'")
+      expect(test_jobs.count).to eq(2)
+      expect(test_jobs.pluck(:name)).to match_array([
+        'test-job: [linux]',
+        'test-job: [windows]'
+      ])
+
+      # Check dependencies are correctly set
+      test_linux = test_jobs.find_by(name: 'test-job: [linux]')
+      test_windows = test_jobs.find_by(name: 'test-job: [windows]')
+      _build_linux = build_jobs.find_by(name: 'build-job: [linux]')
+      _build_windows = build_jobs.find_by(name: 'build-job: [windows]')
+
+      # Each test job should depend only on the corresponding build job
+      expect(test_linux.scheduling_type).to eq('dag')
+      expect(test_linux.needs.map(&:name)).to eq(['build-job: [linux]'])
+
+      expect(test_windows.scheduling_type).to eq('dag')
+      expect(test_windows.needs.map(&:name)).to eq(['build-job: [windows]'])
+    end
+  end
+end