diff --git a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleClassFunctions.java b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleClassFunctions.java
index 5d73246..fd470d0 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleClassFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleClassFunctions.java
@@ -1060,6 +1060,14 @@
       } catch (NameConflictException e) {
         throw new EvalException(e);
       }
+
+      // TODO: #19922 - Instead of evaluating macros synchronously with their declaration, evaluate
+      // them lazily as the targets they declare are requested. But this would mean that targets
+      // declared in a symbolic macro are invisible to native.existing_rules() calls in a legacy
+      // macro. Therefore, this is blocked on either changing the semantics of existing_rules() or
+      // deprecating it entirely.
+      MacroClass.executeMacroImplementation(macroInstance, pkgBuilder, thread.getSemantics());
+
       return Starlark.NONE;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/MacroClass.java b/src/main/java/com/google/devtools/build/lib/packages/MacroClass.java
index f8866bf..a27e645 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/MacroClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/MacroClass.java
@@ -15,9 +15,16 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.server.FailureDetails.PackageLoading.Code;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import javax.annotation.Nullable;
+import net.starlark.java.eval.EvalException;
+import net.starlark.java.eval.Mutability;
+import net.starlark.java.eval.Starlark;
 import net.starlark.java.eval.StarlarkFunction;
+import net.starlark.java.eval.StarlarkSemantics;
+import net.starlark.java.eval.StarlarkThread;
 
 /**
  * Represents a symbolic macro, defined in a .bzl file, that may be instantiated during Package
@@ -65,4 +72,53 @@
       return new MacroClass(name, implementation);
     }
   }
+
+  /**
+   * Executes a symbolic macro's implementation function, in a new Starlark thread, mutating the
+   * given package under construction.
+   */
+  // TODO: #19922 - Take a new type, PackagePiece.Builder, in place of Package.Builder. PackagePiece
+  // would represent the collection of targets/macros instantiated by expanding a single symbolic
+  // macro.
+  public static void executeMacroImplementation(
+      MacroInstance macro, Package.Builder builder, StarlarkSemantics semantics)
+      throws InterruptedException {
+    try (Mutability mu =
+        Mutability.create("macro", builder.getPackageIdentifier(), macro.getName())) {
+      StarlarkThread thread = new StarlarkThread(mu, semantics);
+      thread.setPrintHandler(Event.makeDebugPrintHandler(builder.getLocalEventHandler()));
+
+      new BazelStarlarkContext(
+              BazelStarlarkContext.Phase.LOADING,
+              // TODO: #19922 - Technically we should use a different key than the one in the main
+              // BUILD thread, but that'll be fixed when we change the builder type to
+              // PackagePiece.Builder.
+              new SymbolGenerator<>(builder.getPackageIdentifier()))
+          .storeInThread(thread);
+
+      // TODO: #19922 - Have Package.Builder inherit from BazelStarlarkContext and only store one
+      // thread-local object.
+      thread.setThreadLocal(Package.Builder.class, builder);
+
+      // TODO: #19922 - If we want to support creating analysis_test rules inside symbolic macros,
+      // we'd need to call `thread.setThreadLocal(RuleDefinitionEnvironment.class,
+      // ruleClassProvider)`. In that case we'll need to consider how to get access to the
+      // ConfiguredRuleClassProvider. For instance, we could put it in the builder.
+
+      try {
+        Starlark.fastcall(
+            thread,
+            macro.getMacroClass().getImplementation(),
+            /* positional= */ new Object[] {},
+            /* named= */ new Object[] {"name", macro.getName()});
+      } catch (EvalException ex) {
+        builder
+            .getLocalEventHandler()
+            .handle(
+                Package.error(
+                    /* location= */ null, ex.getMessageWithStack(), Code.STARLARK_EVAL_ERROR));
+        builder.setContainsErrors();
+      }
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index 5b052c0..4ee7c9a 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -1660,8 +1660,6 @@
     public void addMacro(MacroInstance macro) throws NameConflictException {
       checkForExistingName(macro);
       macros.put(macro.getName(), macro);
-      // TODO(#19922): Push to a queue of unexpanded macros, read those when expanding macros as
-      // part of monolithic package evaluation (but not lazy macro evaluation).
     }
 
     void addRegisteredExecutionPlatforms(List<TargetPattern> platforms) {
diff --git a/src/test/java/com/google/devtools/build/lib/packages/SymbolicMacroTest.java b/src/test/java/com/google/devtools/build/lib/packages/SymbolicMacroTest.java
new file mode 100644
index 0000000..cb80376
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/packages/SymbolicMacroTest.java
@@ -0,0 +1,194 @@
+// Copyright 2024 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.packages;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.errorprone.annotations.CanIgnoreReturnValue;
+import javax.annotation.Nullable;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests the execution of symbolic macro implementations. */
+@RunWith(JUnit4.class)
+public final class SymbolicMacroTest extends BuildViewTestCase {
+
+  @Before
+  public void setUp() throws Exception {
+    setBuildLanguageOptions("--experimental_enable_first_class_macros");
+  }
+
+  /**
+   * Returns a package by the given name (no leading "//"), or null upon {@link
+   * NoSuchPackageException}.
+   */
+  @CanIgnoreReturnValue
+  @Nullable
+  private Package getPackage(String pkgName) throws InterruptedException {
+    try {
+      return getPackageManager().getPackage(reporter, PackageIdentifier.createInMainRepo(pkgName));
+    } catch (NoSuchPackageException unused) {
+      return null;
+    }
+  }
+
+  private void assertPackageNotInError(@Nullable Package pkg) {
+    assertThat(pkg).isNotNull();
+    assertThat(pkg.containsErrors()).isFalse();
+  }
+
+  @Test
+  public void implementationIsInvokedWithNameParam() throws Exception {
+    scratch.file(
+        "pkg/foo.bzl", //
+        "def _impl(name):",
+        "    print('my_macro called with name = %s' % name)",
+        "my_macro = macro(implementation=_impl)");
+    scratch.file(
+        "pkg/BUILD", //
+        "load(':foo.bzl', 'my_macro')",
+        "my_macro(name='abc')");
+
+    Package pkg = getPackage("pkg");
+    assertPackageNotInError(pkg);
+    assertContainsEvent("called with name = abc");
+  }
+
+  @Test
+  public void implementationFailsDueToBadSignature() throws Exception {
+    scratch.file(
+        "pkg/foo.bzl", //
+        "def _impl():",
+        "    pass",
+        "my_macro = macro(implementation=_impl)");
+    scratch.file(
+        "pkg/BUILD", //
+        "load(':foo.bzl', 'my_macro')",
+        "my_macro(name='abc')");
+
+    reporter.removeHandler(failFastHandler);
+    Package pkg = getPackage("pkg");
+    assertThat(pkg).isNotNull();
+    assertThat(pkg.containsErrors()).isTrue();
+    assertContainsEvent("_impl() got unexpected keyword argument: name");
+  }
+
+  @Test
+  public void macroCanDeclareTargets() throws Exception {
+    scratch.file(
+        "pkg/foo.bzl", //
+        "def _impl(name):",
+        "    native.cc_library(name = name + '$lib')",
+        "my_macro = macro(implementation=_impl)");
+    scratch.file(
+        "pkg/BUILD", //
+        "load(':foo.bzl', 'my_macro')",
+        "my_macro(name='abc')");
+
+    Package pkg = getPackage("pkg");
+    assertPackageNotInError(pkg);
+    assertThat(pkg.getTargets()).containsKey("abc$lib");
+  }
+
+  @Test
+  public void macroCanDeclareSubmacros() throws Exception {
+    scratch.file(
+        "pkg/foo.bzl", //
+        "def _inner_impl(name):",
+        "    native.cc_library(name = name + '$lib')",
+        "inner_macro = macro(implementation=_inner_impl)",
+        "def _impl(name):",
+        "    inner_macro(name = name + '$inner')",
+        "my_macro = macro(implementation=_impl)");
+    scratch.file(
+        "pkg/BUILD", //
+        "load(':foo.bzl', 'my_macro')",
+        "my_macro(name='abc')");
+
+    Package pkg = getPackage("pkg");
+    assertPackageNotInError(pkg);
+    assertThat(pkg.getTargets()).containsKey("abc$inner$lib");
+  }
+
+  // TODO: #19922 - Invert this, symbolic macros shouldn't be able to call glob().
+  @Test
+  public void macroCanCallGlob() throws Exception {
+    scratch.file("pkg/foo.txt");
+    scratch.file(
+        "pkg/foo.bzl", //
+        "def _impl(name):",
+        "    print('Glob result: %s' % native.glob(['foo*']))",
+        "my_macro = macro(implementation=_impl)");
+    scratch.file(
+        "pkg/BUILD", //
+        "load(':foo.bzl', 'my_macro')",
+        "my_macro(name='abc')");
+
+    Package pkg = getPackage("pkg");
+    assertPackageNotInError(pkg);
+    assertContainsEvent("Glob result: [\"foo.bzl\", \"foo.txt\"]");
+  }
+
+  // TODO: #19922 - Invert this, symbolic macros shouldn't be able to call existing_rules().
+  @Test
+  public void macroCanCallExistingRules() throws Exception {
+    scratch.file(
+        "pkg/foo.bzl", //
+        "def _impl(name):",
+        "    native.cc_binary(name = name + '$lib')",
+        "    print('existing_rules() keys: %s' % native.existing_rules().keys())",
+        "my_macro = macro(implementation=_impl)");
+    scratch.file(
+        "pkg/BUILD", //
+        "load(':foo.bzl', 'my_macro')",
+        "cc_library(name = 'outer_target')",
+        "my_macro(name='abc')");
+
+    Package pkg = getPackage("pkg");
+    assertPackageNotInError(pkg);
+    assertContainsEvent("existing_rules() keys: [\"outer_target\", \"abc$lib\"]");
+  }
+
+  // TODO: #19922 - This behavior is necessary to preserve compatibility with use cases for
+  // native.existing_rules(), but it's a blocker for making symbolic macro evaluation lazy.
+  @Test
+  public void macroDeclaredTargetsAreVisibleToExistingRules() throws Exception {
+    scratch.file(
+        "pkg/foo.bzl", //
+        "def _impl(name):",
+        "    native.cc_binary(name = name + '$lib')",
+        "my_macro = macro(implementation=_impl)",
+        "def query():",
+        "    print('existing_rules() keys: %s' % native.existing_rules().keys())");
+    scratch.file(
+        "pkg/BUILD", //
+        "load(':foo.bzl', 'my_macro', 'query')",
+        "cc_library(name = 'outer_target')",
+        "my_macro(name='abc')",
+        "query()");
+
+    Package pkg = getPackage("pkg");
+    assertPackageNotInError(pkg);
+    assertContainsEvent("existing_rules() keys: [\"outer_target\", \"abc$lib\"]");
+  }
+
+  // TODO: #19922 - Add more test cases for interaction between macros and environment_group,
+  // package_group, implicit/explicit input files, and the package() function. But all of these
+  // behaviors are about to change (from allowed to prohibited).
+}
diff --git a/src/test/java/com/google/devtools/build/lib/starlark/StarlarkRuleClassFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/starlark/StarlarkRuleClassFunctionsTest.java
index 67fab2c..9e48ef4 100644
--- a/src/test/java/com/google/devtools/build/lib/starlark/StarlarkRuleClassFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/starlark/StarlarkRuleClassFunctionsTest.java
@@ -212,7 +212,10 @@
     assertThat(getRuleClass("non_exec_rule").hasAttr("args", Type.STRING_LIST)).isFalse();
   }
 
-  /** Returns a package by the given name (no leading "//"), or null if it was in error. */
+  /**
+   * Returns a package by the given name (no leading "//"), or null upon {@link
+   * NoSuchPackageException}.
+   */
   @CanIgnoreReturnValue
   @Nullable
   private Package getPackage(String pkgName) throws InterruptedException {
@@ -376,9 +379,6 @@
     assertThat(ev.eval("repr(s.unexported)")).isEqualTo("<macro>");
   }
 
-  // TODO(#19922): Add assertions for calling convention and execution of macro implementation
-  // function.
-
   private RuleClass getRuleClass(String name) throws Exception {
     return ((StarlarkRuleFunction) ev.lookup(name)).getRuleClass();
   }