Mycobacterium riyadhense is a newly discovered, slow-growing nontuberculous mycobacterium with an emerging global distribution. We report a case of multifocal osteolytic lesions as the first sign of infection in a previously healthy 39-year-old female. M. riyadhense was detected in this case using next-generation metagenomic sequencing after it failed to be identified with conventional methods. The patient received 12 months of therapy with isoniazid, rifampin, and ethambutol, with the addition of moxifloxacin and clarithromycin in the first four months, and had a full return to health with no detectable disease at the last follow-up.