diff --git a/app/src/main/java/com/stevesoltys/seedvault/App.kt b/app/src/main/java/com/stevesoltys/seedvault/App.kt
index e91e7c8..295f906 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/App.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/App.kt
@@ -44,7 +44,7 @@
         factory { AppListRetriever(this@App, get(), get(), get()) }
 
         viewModel { SettingsViewModel(this@App, get(), get(), get(), get(), get()) }
-        viewModel { RecoveryCodeViewModel(this@App, get(), get()) }
+        viewModel { RecoveryCodeViewModel(this@App, get(), get(), get()) }
         viewModel { BackupStorageViewModel(this@App, get(), get(), get()) }
         viewModel { RestoreStorageViewModel(this@App, get(), get()) }
         viewModel { RestoreViewModel(this@App, get(), get(), get(), get(), get()) }
diff --git a/app/src/main/java/com/stevesoltys/seedvault/plugins/saf/DocumentsProviderBackupPlugin.kt b/app/src/main/java/com/stevesoltys/seedvault/plugins/saf/DocumentsProviderBackupPlugin.kt
index c71d450..9789b43 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/plugins/saf/DocumentsProviderBackupPlugin.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/plugins/saf/DocumentsProviderBackupPlugin.kt
@@ -45,6 +45,11 @@
     }
 
     @Throws(IOException::class)
+    override suspend fun deleteAllBackups() {
+        storage.rootBackupDir?.deleteContents(context)
+    }
+
+    @Throws(IOException::class)
     override suspend fun getMetadataOutputStream(): OutputStream {
         val setDir = storage.getSetDir() ?: throw IOException()
         val metadataFile = setDir.createOrGetFile(context, FILE_BACKUP_METADATA)
diff --git a/app/src/main/java/com/stevesoltys/seedvault/transport/backup/BackupPlugin.kt b/app/src/main/java/com/stevesoltys/seedvault/transport/backup/BackupPlugin.kt
index f867250..5a08a63 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/transport/backup/BackupPlugin.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/transport/backup/BackupPlugin.kt
@@ -26,6 +26,12 @@
     suspend fun initializeDevice()
 
     /**
+     * Delete all existing [RestoreSet]s from the storage medium.
+     */
+    @Throws(IOException::class)
+    suspend fun deleteAllBackups()
+
+    /**
      * Returns an [OutputStream] for writing backup metadata.
      */
     @Throws(IOException::class)
diff --git a/app/src/main/java/com/stevesoltys/seedvault/ui/recoverycode/RecoveryCodeInputFragment.kt b/app/src/main/java/com/stevesoltys/seedvault/ui/recoverycode/RecoveryCodeInputFragment.kt
index 15c1d5a..94f0b3c 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/ui/recoverycode/RecoveryCodeInputFragment.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/ui/recoverycode/RecoveryCodeInputFragment.kt
@@ -190,6 +190,7 @@
 
     private val regenRequest = registerForActivityResult(StartActivityForResult()) {
         if (it.resultCode == RESULT_OK) {
+            viewModel.deleteAllBackup()
             parentFragmentManager.popBackStack()
             Snackbar.make(requireView(), R.string.recovery_code_recreated, Snackbar.LENGTH_LONG)
                 .show()
@@ -203,7 +204,6 @@
             .setMessage(R.string.recovery_code_verification_new_dialog_message)
             .setPositiveButton(R.string.recovery_code_verification_generate_new) { dialog, _ ->
                 dialog.dismiss()
-                // TODO try to delete backups
                 val i = Intent(requireContext(), RecoveryCodeActivity::class.java)
                 regenRequest.launch(i)
             }
diff --git a/app/src/main/java/com/stevesoltys/seedvault/ui/recoverycode/RecoveryCodeViewModel.kt b/app/src/main/java/com/stevesoltys/seedvault/ui/recoverycode/RecoveryCodeViewModel.kt
index 90ff889..74f9d75 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/ui/recoverycode/RecoveryCodeViewModel.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/ui/recoverycode/RecoveryCodeViewModel.kt
@@ -1,9 +1,11 @@
 package com.stevesoltys.seedvault.ui.recoverycode
 
+import android.util.Log
 import androidx.lifecycle.AndroidViewModel
 import com.stevesoltys.seedvault.App
 import com.stevesoltys.seedvault.crypto.Crypto
 import com.stevesoltys.seedvault.crypto.KeyManager
+import com.stevesoltys.seedvault.transport.backup.BackupPlugin
 import com.stevesoltys.seedvault.ui.LiveEvent
 import com.stevesoltys.seedvault.ui.MutableLiveEvent
 import io.github.novacrypto.bip39.JavaxPBKDF2WithHmacSHA512
@@ -16,6 +18,10 @@
 import io.github.novacrypto.bip39.Validation.WordNotFoundException
 import io.github.novacrypto.bip39.Words
 import io.github.novacrypto.bip39.wordlists.English
+import kotlinx.coroutines.Dispatchers
+import kotlinx.coroutines.GlobalScope
+import kotlinx.coroutines.launch
+import java.io.IOException
 import java.security.SecureRandom
 import java.util.ArrayList
 
@@ -25,7 +31,8 @@
 class RecoveryCodeViewModel(
     app: App,
     private val crypto: Crypto,
-    private val keyManager: KeyManager
+    private val keyManager: KeyManager,
+    private val backupPlugin: BackupPlugin
 ) : AndroidViewModel(app) {
 
     internal val wordList: List<CharSequence> by lazy {
@@ -69,4 +76,14 @@
         }
     }
 
+    fun deleteAllBackup() {
+        GlobalScope.launch(Dispatchers.IO) {
+            try {
+                backupPlugin.deleteAllBackups()
+            } catch (e: IOException) {
+                Log.e("RecoveryCodeViewModel", "Error deleting backups", e)
+            }
+        }
+    }
+
 }