diff --git a/src/main/java/com/android/tools/r8/cf/code/CfCheckCast.java b/src/main/java/com/android/tools/r8/cf/code/CfCheckCast.java
index 6c30ad3..bec1872 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfCheckCast.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfCheckCast.java
@@ -144,4 +144,14 @@
     DexItemFactory dexItemFactory = appView.dexItemFactory();
     return frame.popInitialized(appView, config, dexItemFactory.objectType).push(config, type);
   }
+
+  @Override
+  public boolean isCheckCast() {
+    return true;
+  }
+
+  @Override
+  public CfCheckCast asCheckCast() {
+    return this;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java b/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
index b137991..f21fc0c 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
@@ -412,4 +412,12 @@
 
   public abstract CfFrameState evaluate(
       CfFrameState frame, AppView<?> appView, CfAnalysisConfig config);
+
+  public boolean isCheckCast() {
+    return false;
+  }
+
+  public CfCheckCast asCheckCast() {
+    return null;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java b/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java
index 3050bdc..dfbfc0e 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java
@@ -8,6 +8,7 @@
 
 import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
 import com.android.tools.r8.androidapi.ComputedApiLevel;
+import com.android.tools.r8.cf.code.CfCheckCast;
 import com.android.tools.r8.cf.code.CfFieldInstruction;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.cf.code.CfInvoke;
@@ -24,6 +25,7 @@
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexTypeList;
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaring;
@@ -31,6 +33,7 @@
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer;
 import com.android.tools.r8.ir.desugar.FreshLocalProvider;
 import com.android.tools.r8.ir.desugar.LocalStackAllocator;
+import com.android.tools.r8.ir.synthetic.CheckCastSourceCode;
 import com.android.tools.r8.ir.synthetic.FieldAccessorBuilder;
 import com.android.tools.r8.ir.synthetic.ForwardMethodBuilder;
 import com.android.tools.r8.synthesis.SyntheticMethodBuilder;
@@ -51,9 +54,12 @@
   private final AppView<?> appView;
   private final AndroidApiLevelCompute apiLevelCompute;
 
+  private final DexTypeList objectParams;
+
   public ApiInvokeOutlinerDesugaring(AppView<?> appView, AndroidApiLevelCompute apiLevelCompute) {
     this.appView = appView;
     this.apiLevelCompute = apiLevelCompute;
+    this.objectParams = DexTypeList.create(new DexType[] {appView.dexItemFactory().objectType});
   }
 
   @Override
@@ -91,9 +97,6 @@
 
   private ComputedApiLevel getComputedApiLevelInstructionOnHolderWithMinApi(
       CfInstruction instruction) {
-    if (!instruction.isInvoke() && !instruction.isFieldInstruction()) {
-      return appView.computedMinApiLevel();
-    }
     DexReference reference;
     if (instruction.isInvoke()) {
       CfInvoke cfInvoke = instruction.asInvoke();
@@ -101,8 +104,12 @@
         return appView.computedMinApiLevel();
       }
       reference = cfInvoke.getMethod();
-    } else {
+    } else if (instruction.isFieldInstruction()) {
       reference = instruction.asFieldInstruction().getField();
+    } else if (instruction.isCheckCast()) {
+      reference = instruction.asCheckCast().getType();
+    } else {
+      return appView.computedMinApiLevel();
     }
     if (!reference.getContextType().isClassType()) {
       return appView.computedMinApiLevel();
@@ -119,7 +126,7 @@
       return appView.computedMinApiLevel();
     }
     // Check for protected or package private access flags before outlining.
-    if (holder.isInterface()) {
+    if (holder.isInterface() || instruction.isCheckCast()) {
       return referenceApiLevel;
     } else {
       DexEncodedMember<?, ?> definition =
@@ -167,7 +174,7 @@
       DexItemFactory factory,
       ApiInvokeOutlinerDesugaringEventConsumer eventConsumer,
       ProgramMethod context) {
-    assert instruction.isInvoke() || instruction.isFieldInstruction();
+    assert instruction.isInvoke() || instruction.isFieldInstruction() || instruction.isCheckCast();
     ProgramMethod outlinedMethod =
         ensureOutlineMethod(uniqueContext, instruction, computedApiLevel, factory, context);
     eventConsumer.acceptOutlinedMethod(outlinedMethod, context);
@@ -199,6 +206,8 @@
                   .setApiLevelForCode(apiLevel);
               if (instruction.isInvoke()) {
                 setCodeForInvoke(syntheticMethodBuilder, instruction.asInvoke(), factory);
+              } else if (instruction.isCheckCast()) {
+                setCodeForCheckCast(syntheticMethodBuilder, instruction.asCheckCast(), factory);
               } else {
                 assert instruction.isCfInstruction();
                 setCodeForFieldInstruction(
@@ -273,6 +282,18 @@
                     .build());
   }
 
+  private void setCodeForCheckCast(
+      SyntheticMethodBuilder methodBuilder, CfCheckCast instruction, DexItemFactory factory) {
+    DexClass target = appView.definitionFor(instruction.getType());
+    assert target != null;
+    methodBuilder
+        .setProto(factory.createProto(target.getType(), objectParams))
+        .setCode(
+            m ->
+                CheckCastSourceCode.create(appView, m.getHolderType(), target.getType())
+                    .generateCfCode());
+  }
+
   private boolean verifyLibraryHolderAndInvoke(
       DexClass libraryHolder, DexMethod apiMethod, boolean isVirtualInvoke) {
     DexEncodedMethod libraryApiMethodDefinition = libraryHolder.lookupMethod(apiMethod);
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/CheckCastSourceCode.java b/src/main/java/com/android/tools/r8/ir/synthetic/CheckCastSourceCode.java
new file mode 100644
index 0000000..32fe7c5
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/CheckCastSourceCode.java
@@ -0,0 +1,41 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.synthetic;
+
+import com.android.tools.r8.cf.code.CfCheckCast;
+import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.cf.code.CfLoad;
+import com.android.tools.r8.cf.code.CfReturn;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.ValueType;
+import java.util.ArrayList;
+import java.util.List;
+
+// Source code representing a simple call to CheckCast.
+public final class CheckCastSourceCode extends SyntheticCfCodeProvider {
+
+  private final DexType checkCastType;
+
+  private CheckCastSourceCode(AppView<?> appView, DexType holder, DexType checkCastType) {
+    super(appView, holder);
+    this.checkCastType = checkCastType;
+  }
+
+  public static CheckCastSourceCode create(
+      AppView<?> appView, DexType holder, DexType checkCastType) {
+    return new CheckCastSourceCode(appView, holder, checkCastType);
+  }
+
+  @Override
+  public CfCode generateCfCode() {
+    List<CfInstruction> instructions = new ArrayList<>();
+    instructions.add(new CfLoad(ValueType.OBJECT, 0));
+    instructions.add(new CfCheckCast(checkCastType));
+    instructions.add(new CfReturn(ValueType.OBJECT));
+    return standardCfCodeFromInstructions(instructions);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/ComputeApiLevelUseRegistry.java b/src/main/java/com/android/tools/r8/shaking/ComputeApiLevelUseRegistry.java
index fcd894d..e9857a0 100644
--- a/src/main/java/com/android/tools/r8/shaking/ComputeApiLevelUseRegistry.java
+++ b/src/main/java/com/android/tools/r8/shaking/ComputeApiLevelUseRegistry.java
@@ -118,12 +118,12 @@
 
   @Override
   public void registerCheckCast(DexType type, boolean ignoreCompatRules) {
-    // CheckCast are not causing soft verification issues
+    setMaxApiReferenceLevel(type);
   }
 
   @Override
   public void registerSafeCheckCast(DexType type) {
-    // CheckCast are not causing soft verification issues
+    setMaxApiReferenceLevel(type);
   }
 
   @Override
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelFieldTypeReferenceTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelFieldTypeReferenceTest.java
index f946a84..75e1da7 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelFieldTypeReferenceTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelFieldTypeReferenceTest.java
@@ -51,14 +51,20 @@
         .apply(
             addTracedApiReferenceLevelCallBack(
                 (method, apiLevel) -> {
-                  if (Reference.methodFromMethod(readApiField).equals(method)
-                      || Reference.methodFromMethod(setApiField).equals(method)) {
+                  if (Reference.methodFromMethod(readApiField).equals(method)) {
                     if (parameters.isCfRuntime()) {
                       assertEquals(AndroidApiLevel.B, apiLevel);
                     } else {
                       assertEquals(AndroidApiLevel.B.max(parameters.getApiLevel()), apiLevel);
                     }
                   }
+                  if (Reference.methodFromMethod(setApiField).equals(method)) {
+                    if (parameters.isCfRuntime()) {
+                      assertEquals(AndroidApiLevel.L_MR1, apiLevel);
+                    } else {
+                      assertEquals(AndroidApiLevel.L_MR1.max(parameters.getApiLevel()), apiLevel);
+                    }
+                  }
                 }))
         .compile()
         .addRunClasspathClasses(Api.class)
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelInlineMethodWithApiTypeTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelInlineMethodWithApiTypeTest.java
index 73132ae..2a0d763 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelInlineMethodWithApiTypeTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelInlineMethodWithApiTypeTest.java
@@ -5,8 +5,8 @@
 package com.android.tools.r8.apimodel;
 
 import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
-import static com.android.tools.r8.apimodel.ApiModelingTestHelper.verifyThat;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
 import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
 
@@ -38,7 +38,6 @@
   @Test
   public void testR8() throws Exception {
     Method apiCallerApiLevel22 = ApiCaller.class.getDeclaredMethod("apiLevel22");
-    Method apiCallerCallerApiLevel22 = ApiCallerCaller.class.getDeclaredMethod("apiLevel22");
     testForR8(parameters.getBackend())
         .addProgramClasses(ApiCaller.class, ApiCallerCaller.class, OtherCaller.class, Main.class)
         .addLibraryClasses(ApiType.class)
@@ -55,8 +54,14 @@
         .assertSuccessWithOutputLines(ApiType.class.getName())
         .inspect(
             inspector -> {
-              verifyThat(inspector, parameters, apiCallerApiLevel22)
-                  .inlinedInto(apiCallerCallerApiLevel22);
+              assertThat(
+                  inspector.method(apiCallerApiLevel22),
+                  notIf(
+                      isPresent(),
+                      parameters.isDexRuntime()
+                          && parameters
+                              .getApiLevel()
+                              .isGreaterThanOrEqualTo(AndroidApiLevel.L_MR1)));
               assertThat(inspector.clazz(OtherCaller.class), not(isPresent()));
             });
   }
@@ -68,7 +73,7 @@
 
     public static ApiType apiLevel22() throws Exception {
       // The reflective call here is to ensure that the setting of A's api level is not based on
-      // a method reference to `Api` and only because of the type reference in the field `api`.
+      // a method reference to `Api` and only because of the type reference in the checkcast.
       Class<?> reflectiveCall =
           Class.forName(
               "com.android.tools.r8.apimodel.ApiModelInlineMethodWithApiTypeTest_ApiType"
@@ -82,7 +87,7 @@
 
     public static void apiLevel22() throws Exception {
       // This is referencing the proto of ApiCaller.foo and thus have a reference to ApiType. It is
-      // therefore OK to inline ApiCaller.foo() into ApiCallerCaller.bar().
+      // therefore OK to inline ApiCaller.apiLevel22() into ApiCallerCaller.apiLevel22().
       System.out.println(ApiCaller.apiLevel22().getClass().getName());
     }
   }
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelMethodTypeReferenceTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelMethodTypeReferenceTest.java
index 53b4942..5df420d 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelMethodTypeReferenceTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelMethodTypeReferenceTest.java
@@ -51,14 +51,20 @@
         .apply(
             addTracedApiReferenceLevelCallBack(
                 (method, apiLevel) -> {
-                  if (Reference.methodFromMethod(readApi).equals(method)
-                      || Reference.methodFromMethod(setApi).equals(method)) {
+                  if (Reference.methodFromMethod(readApi).equals(method)) {
                     if (parameters.isCfRuntime()) {
                       assertEquals(AndroidApiLevel.B, apiLevel);
                     } else {
                       assertEquals(AndroidApiLevel.B.max(parameters.getApiLevel()), apiLevel);
                     }
                   }
+                  if (Reference.methodFromMethod(setApi).equals(method)) {
+                    if (parameters.isCfRuntime()) {
+                      assertEquals(AndroidApiLevel.L_MR1, apiLevel);
+                    } else {
+                      assertEquals(AndroidApiLevel.L_MR1.max(parameters.getApiLevel()), apiLevel);
+                    }
+                  }
                 }))
         .compile()
         .addRunClasspathClasses(Api.class)
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelNoInliningOfHigherApiLevelInterfaceTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelNoInliningOfHigherApiLevelInterfaceTest.java
index 22a7321..dec0a00 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelNoInliningOfHigherApiLevelInterfaceTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelNoInliningOfHigherApiLevelInterfaceTest.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.apimodel;
 
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
 import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForMethod;
 import static com.android.tools.r8.apimodel.ApiModelingTestHelper.verifyThat;
 
@@ -48,6 +49,7 @@
         .enableConstantArgumentAnnotations()
         .enableInliningAnnotations()
         .enableNoHorizontalClassMergingAnnotations()
+        .apply(setMockApiLevelForClass(Api.class, AndroidApiLevel.L_MR1))
         .apply(setMockApiLevelForMethod(apiMethod, AndroidApiLevel.L_MR1))
         .apply(ApiModelingTestHelper::enableApiCallerIdentification)
         // We are testing that we do not inline/merge higher api-levels
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineCheckCastTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineCheckCastTest.java
index dfb1a23..663a649 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineCheckCastTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineCheckCastTest.java
@@ -85,7 +85,7 @@
         .setMode(CompilationMode.DEBUG)
         .apply(this::setupTestBuilder)
         .compile()
-        .inspect(inspector -> inspect(inspector, false))
+        .inspect(this::inspect)
         .applyIf(
             addToBootClasspath(),
             b -> b.addBootClasspathClasses(LibraryClass.class, LibraryProvider.class),
@@ -101,7 +101,7 @@
         .setMode(CompilationMode.RELEASE)
         .apply(this::setupTestBuilder)
         .compile()
-        .inspect(inspector -> inspect(inspector, false))
+        .inspect(this::inspect)
         .applyIf(
             addToBootClasspath(),
             b -> b.addBootClasspathClasses(LibraryClass.class, LibraryProvider.class),
@@ -116,7 +116,7 @@
         .apply(this::setupTestBuilder)
         .addKeepMainRule(Main.class)
         .compile()
-        .inspect(inspector -> inspect(inspector, true))
+        .inspect(this::inspect)
         .applyIf(
             addToBootClasspath(),
             b -> b.addBootClasspathClasses(LibraryClass.class, LibraryProvider.class),
@@ -125,10 +125,9 @@
         .apply(this::checkOutput);
   }
 
-  private void inspect(CodeInspector inspector, boolean isR8) throws Exception {
+  private void inspect(CodeInspector inspector) throws Exception {
     verifyThat(inspector, parameters, LibraryClass.class)
-        // TODO(b/b/258270051): We should outline the check cast.
-        .hasNotCheckCastOutlinedFrom(Main.class.getMethod("main", String[].class));
+        .hasCheckCastOutlinedFromUntil(Main.class.getMethod("main", String[].class), classApiLevel);
   }
 
   private void checkOutput(SingleTestRunResult<?> runResult) {
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelTypeReferenceInvokeTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelTypeReferenceInvokeTest.java
index 79df3a4..8d59924 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelTypeReferenceInvokeTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelTypeReferenceInvokeTest.java
@@ -6,7 +6,8 @@
 
 import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
 import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForMethod;
-import static com.android.tools.r8.apimodel.ApiModelingTestHelper.verifyThat;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isAbsent;
+import static org.hamcrest.MatcherAssert.assertThat;
 
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.TestBase;
@@ -34,8 +35,6 @@
   @Test
   public void testR8() throws Exception {
     Method apiMethod = LibraryClass.class.getDeclaredMethod("apiMethod");
-    Method apiCaller = ApiHelper.class.getDeclaredMethod("apiCaller", LibraryClass.class);
-    Method apiCallerCaller = Main.class.getDeclaredMethod("typeReference", Object.class);
     boolean libraryClassOnBoot =
         parameters.isDexRuntime()
             && parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.M);
@@ -53,10 +52,7 @@
         .enableInliningAnnotations()
         .addAndroidBuildVersion()
         .compile()
-        .inspect(
-            inspector ->
-                verifyThat(inspector, parameters, apiCaller)
-                    .inlinedIntoFromApiLevel(apiCallerCaller, AndroidApiLevel.M))
+        .inspect(inspector -> assertThat(inspector.clazz(ApiHelper.class), isAbsent()))
         .addRunClasspathClasses(LibraryClass.class)
         .run(parameters.getRuntime(), Main.class)
         .assertSuccessWithOutputLinesIf(