diff --git a/crypto/evp/evp_fetch.c b/crypto/evp/evp_fetch.c
index 5fe9c7e..e3c43f4 100644
--- a/crypto/evp/evp_fetch.c
+++ b/crypto/evp/evp_fetch.c
@@ -418,6 +418,16 @@
     return 1;
 }
 
+int evp_method_store_remove_all_provided(const OSSL_PROVIDER *prov)
+{
+    OSSL_LIB_CTX *libctx = ossl_provider_libctx(prov);
+    OSSL_METHOD_STORE *store = get_evp_method_store(libctx);
+
+    if (store != NULL)
+        return ossl_method_store_remove_all_provided(store, prov);
+    return 1;
+}
+
 static int evp_set_parsed_default_properties(OSSL_LIB_CTX *libctx,
                                              OSSL_PROPERTY_LIST *def_prop,
                                              int loadconfig,
diff --git a/crypto/property/property.c b/crypto/property/property.c
index b2c71db..4303b4b 100644
--- a/crypto/property/property.c
+++ b/crypto/property/property.c
@@ -89,6 +89,8 @@
 #endif
 } OSSL_GLOBAL_PROPERTIES;
 
+static void ossl_method_cache_flush_alg(OSSL_METHOD_STORE *store,
+                                        ALGORITHM *alg);
 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid);
 
 /* Global properties are stored per library context */
@@ -197,6 +199,12 @@
     }
 }
 
+static void impl_cache_flush_alg(ossl_uintmax_t idx, ALGORITHM *alg)
+{
+    lh_QUERY_doall(alg->cache, &impl_cache_free);
+    lh_QUERY_flush(alg->cache);
+}
+
 static void alg_cleanup(ossl_uintmax_t idx, ALGORITHM *a)
 {
     if (a != NULL) {
@@ -366,6 +374,55 @@
     return 0;
 }
 
+struct alg_cleanup_by_provider_data_st {
+    OSSL_METHOD_STORE *store;
+    const OSSL_PROVIDER *prov;
+};
+
+static void
+alg_cleanup_by_provider(ossl_uintmax_t idx, ALGORITHM *alg, void *arg)
+{
+    struct alg_cleanup_by_provider_data_st *data = arg;
+    int i, count;
+
+    /*
+     * We walk the stack backwards, to avoid having to deal with stack shifts
+     * caused by deletion
+     */
+    for (count = 0, i = sk_IMPLEMENTATION_num(alg->impls); i-- > 0;) {
+        IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
+
+        if (impl->provider == data->prov) {
+            impl_free(impl);
+            (void)sk_IMPLEMENTATION_delete(alg->impls, i);
+            count++;
+        }
+    }
+
+    /*
+     * If we removed any implementation, we also clear the whole associated
+     * cache, 'cause that's the sensible thing to do.
+     * There's no point flushing the cache entries where we didn't remove
+     * any implementation, though.
+     */
+    if (count > 0)
+        ossl_method_cache_flush_alg(data->store, alg);
+}
+
+int ossl_method_store_remove_all_provided(OSSL_METHOD_STORE *store,
+                                          const OSSL_PROVIDER *prov)
+{
+    struct alg_cleanup_by_provider_data_st data;
+
+    if (!ossl_property_write_lock(store))
+        return 0;
+    data.prov = prov;
+    data.store = store;
+    ossl_sa_ALGORITHM_doall_arg(store->algs, &alg_cleanup_by_provider, &data);
+    ossl_property_unlock(store);
+    return 1;
+}
+
 static void alg_do_one(ALGORITHM *alg, IMPLEMENTATION *impl,
                        void (*fn)(int id, void *method, void *fnarg),
                        void *fnarg)
@@ -484,20 +541,19 @@
     return ret;
 }
 
-static void impl_cache_flush_alg(ossl_uintmax_t idx, ALGORITHM *alg)
+static void ossl_method_cache_flush_alg(OSSL_METHOD_STORE *store,
+                                        ALGORITHM *alg)
 {
-    lh_QUERY_doall(alg->cache, &impl_cache_free);
-    lh_QUERY_flush(alg->cache);
+    store->cache_nelem -= lh_QUERY_num_items(alg->cache);
+    impl_cache_flush_alg(0, alg);
 }
 
 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid)
 {
     ALGORITHM *alg = ossl_method_store_retrieve(store, nid);
 
-    if (alg != NULL) {
-        store->cache_nelem -= lh_QUERY_num_items(alg->cache);
-        impl_cache_flush_alg(0, alg);
-    }
+    if (alg != NULL)
+        ossl_method_cache_flush_alg(store, alg);
 }
 
 int ossl_method_store_cache_flush_all(OSSL_METHOD_STORE *store)
diff --git a/crypto/provider_core.c b/crypto/provider_core.c
index ef0c156..8e7ed62 100644
--- a/crypto/provider_core.c
+++ b/crypto/provider_core.c
@@ -1156,6 +1156,30 @@
     return 1;
 }
 
+static int provider_remove_store_methods(OSSL_PROVIDER *prov)
+{
+    struct provider_store_st *store;
+    int freeing;
+
+    if ((store = get_provider_store(prov->libctx)) == NULL)
+        return 0;
+
+    if (!CRYPTO_THREAD_read_lock(store->lock))
+        return 0;
+    freeing = store->freeing;
+    CRYPTO_THREAD_unlock(store->lock);
+
+    if (!freeing) {
+        OPENSSL_free(prov->operation_bits);
+        prov->operation_bits = NULL;
+        prov->operation_bits_sz = 0;
+        CRYPTO_THREAD_unlock(prov->opbits_lock);
+
+        return evp_method_store_remove_all_provided(prov);
+    }
+    return 1;
+}
+
 int ossl_provider_activate(OSSL_PROVIDER *prov, int upcalls, int aschild)
 {
     int count;
@@ -1183,7 +1207,7 @@
     if (prov == NULL
             || (count = provider_deactivate(prov, 1, removechildren)) < 0)
         return 0;
-    return count == 0 ? provider_flush_store_cache(prov) : 1;
+    return count == 0 ? provider_remove_store_methods(prov) : 1;
 }
 
 void *ossl_provider_ctx(const OSSL_PROVIDER *prov)
@@ -1482,7 +1506,7 @@
         return 1;
     ret = prov->self_test(prov->provctx);
     if (ret == 0)
-        (void)provider_flush_store_cache(prov);
+        (void)provider_remove_store_methods((OSSL_PROVIDER *)prov);
     return ret;
 }
 
diff --git a/doc/internal/man3/OSSL_METHOD_STORE.pod b/doc/internal/man3/OSSL_METHOD_STORE.pod
index a4c1c1b..70f6eb5 100644
--- a/doc/internal/man3/OSSL_METHOD_STORE.pod
+++ b/doc/internal/man3/OSSL_METHOD_STORE.pod
@@ -4,9 +4,10 @@
 
 OSSL_METHOD_STORE, ossl_method_store_new, ossl_method_store_free,
 ossl_method_store_init, ossl_method_store_cleanup,
-ossl_method_store_add, ossl_method_store_remove, ossl_method_store_fetch,
+ossl_method_store_add, ossl_method_store_fetch,
+ossl_method_store_remove, ossl_method_store_remove_all_provided, 
 ossl_method_store_cache_get, ossl_method_store_cache_set,
-ossl_method_store_flush_cache
+ossl_method_store_cache_flush_all
 - implementation method store and query
 
 =head1 SYNOPSIS
@@ -28,6 +29,9 @@
  int ossl_method_store_fetch(OSSL_METHOD_STORE *store,
                              int nid, const char *properties,
                              void **method, const OSSL_PROVIDER **prov_rw);
+ int ossl_method_store_remove_all_provided(OSSL_METHOD_STORE *store,
+                                           const OSSL_PROVIDER *prov);
+
  int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, OSSL_PROVIDER *prov,
                                  int nid, const char *prop_query, void **method);
  int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, OSSL_PROVIDER *prov,
@@ -83,6 +87,10 @@
 to methods from that provider.
 The result, if any, is returned in I<*method>, and its provider in I<*prov>.
 
+ossl_method_store_remove_all_provided() removes all methods from I<store>
+that are provided by I<prov>.
+When doing so, it also flushes the corresponding cache entries.
+
 =head2 Cache Functions
 
 ossl_method_store_cache_get() queries the cache associated with the I<store>
diff --git a/include/crypto/evp.h b/include/crypto/evp.h
index b00cd8c..845c62e 100644
--- a/include/crypto/evp.h
+++ b/include/crypto/evp.h
@@ -894,6 +894,7 @@
 # endif /* !defined(FIPS_MODULE) */
 
 int evp_method_store_cache_flush(OSSL_LIB_CTX *libctx);
+int evp_method_store_remove_all_provided(const OSSL_PROVIDER *prov);
 
 int evp_default_properties_enable_fips_int(OSSL_LIB_CTX *libctx, int enable,
                                            int loadconfig);
diff --git a/include/internal/property.h b/include/internal/property.h
index 9c68e8c..db08c33 100644
--- a/include/internal/property.h
+++ b/include/internal/property.h
@@ -64,6 +64,8 @@
 int ossl_method_store_fetch(OSSL_METHOD_STORE *store,
                             int nid, const char *prop_query,
                             const OSSL_PROVIDER **prov, void **method);
+int ossl_method_store_remove_all_provided(OSSL_METHOD_STORE *store,
+                                          const OSSL_PROVIDER *prov);
 
 /* Get the global properties associate with the specified library context */
 OSSL_PROPERTY_LIST **ossl_ctx_global_properties(OSSL_LIB_CTX *ctx,