Locked out of MFA due to new phone - I am only admin, all suggestions already attempted

Hi @Julie Teplitzky (Consultant), 

Thank you for reaching out to Microsoft Q&A forum. 

Regarding your issue, you're currently unable to access your account because the Microsoft Authenticator app is still linked to a previous device, and you're not receiving the authentication code needed to sign in.  

Here is a workaround to regain control your account, the best next step is to contact Microsoft Support directly so we can securely verify your account and assist with reactivating access to your new device. 

Because you are the sole admin of your tenant with no access, you will need involvement from Data Protection team.    

Please note that forum moderators do not have access to user account settings and cannot assist with logging in, resetting passwords, or changing access rights. While we do not have access to internal systems or administrative tools required to resolve account-specific or backend-related issues but we’ll continue doing our best to support you within the scope of our responsibilities.       

You can contact them via phone number to Microsoft Support:     

• Visit Customer service phone numbers - Microsoft Support 
• Select your country/region own phone number for support.

If you're struggling with the AI call sequence, please follow this dialogue    

IIVR: What kind of problem are you concerned about?        

You: Authenticator.        

IVR: What kind of product do you use?        

You: Office 365 for business.        

IVR confirmation: education or company account?        

You: For companies       

IVR: Are you an administrator?        

You: Yes.        

IVR: Do you have the other administrator in your organization?        

You: No. I am the only admin in my tenant        

IVR: Do you need a... Service request?        

You: Yes. I need to create a ticket. Please send me direct to the Data Protection Teams.     

After you revoke your current multi-factor authentication (MFA) session, you can follow these steps to set up the Microsoft Authenticator app again on your new device:   

1. Download and install the app from the App Store (iOS) or Google Play Store (Android).   
2. Go to aka.ms/mfasetup on a browser and sign in with your business account.   
3. On the Start by getting the app page, then select Next.    

4. Remain on the Set up your account page while you set up the Microsoft Authenticator app on your mobile device.   

5. Open the Microsoft Authenticator app, select to allow notifications (if prompted), select Add account from the Customize and control icon on the upper-right, and then select Work or school account.   
6. Return to the Set up your account page on your computer, and then select Next. The Scan the QR code page appears.   
7. Scan the provided code with the Microsoft Authenticator app QR code reader.   

8. Select Next on the Scan the QR code page on your computer. A notification is sent to the Microsoft Authenticator app on your mobile device, to test your account.   

9. Approve the notification in the Microsoft Authenticator app, and then select Next. Your security info is updated to use the Microsoft Authenticator app by default to verify your identity when using two-step verification or password reset.   

10. From now, you just re-add/register your authentication method and let's check it.   

Once completed, your account will be protected again with MFA, and you’ll be able to sign in securely using the new device.   

I hope this helps resolve the issue you're facing smoothly. I'm happy to assist and truly hope the information provided has been clear and useful. Please feel free to reach out anytime if you need further support. 

If you find this post helpful, kindly consider marking it as the accepted answer. Doing so can assist others in the community who may have similar questions in finding solutions more quickly. 

Thank you for your kindness and contributions to the forum. 

If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".  

Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.  

Sorry, no, I have done all of the above and the nail in my coffin was changing my password... I called all of those numbers and even sat on hold for 2 hours waiting for data security and was hung up on. I have tickets filed. All of the very clear options have been exhausted. I need data security to actually ANSWER the ticket and call me back. This is a wildly unacceptable glitch in the system that I can see from other forums MANY people are experiencing.