The Danish 13th seed had retired injured from her two previous matches in the lead-up to Roland Garros, but looked to have found form in a one-sided opening set.
Last year's Australian Open champion lost her way in the second set, though, making 10 unforced errors, but said her opponent was fortunate to turn the match around.
"I think she got very lucky at the start of the second set and took advantage of the opportunities she got," said Wozniacki.
"I ran out of steam in the end and made some unforced errors that I don't usually do, so that was very frustrating.
"She had a few net chords and good shots on some of the important points at the start of the second set.
"It's definitely frustrating. You want to win, you work hard and you want to see results.
"It hasn't been a great year for me so far, so I'm going to work hard and try and turn it around."
The 22-year-old Kudermetova cruised to victory in the decider on a sparsely-populated Court Philippe Chatrier to claim the biggest win of her career.
She will face either Kazakhstan's Zarina Diyas or French wildcard Audrey Albie in the second round, having only made her main-draw debut at a Grand Slam event with a first-round Australian Open loss in January.
"I was a little bit nervous at the start of the match, but I took it game by game and tried to be more aggressive," said the Russian.
For Wozniacki now, her focus will turn to the grass-court season, in which she has struggled in the past -- never having reached the Wimbledon quarter-finals.
"I haven't had the best lead-up to this tournament," she said.
"I had a calf injury so haven't really been able to play or practise for a couple of weeks.
"My calf now feels good so that's a positive so I'm definitely going to go back and work hard and get ready for the grass season."
It was the first time Wozniacki had lost in the opening round of a Grand Slam tournament since Wimbledon three years ago.
"I just have to try and stay positive, and obviously it's not as easy to stay positive when things aren't going your way," she added.
Results from the second day of the French Open on Monday (x denotes seeding):
Novak Djokovic (SRB x1) bt Hubert Hurkacz (POL) 6-4, 6-2, 6-2
Henri Laaksonen (SUI) bt Pedro Martinez (ESP) 6-1, 6-0, 7-6 (7/4)
Salvatore Caruso (ITA) bt Jaume Munar (ESP) 7-5, 4-6, 6-3, 6-3
Gilles Simon (FRA x26) bt Sergiy Stakhovsky (UKR) 6-3, 6-3, 6-4
Jan-Lennard Struff (GER) bt Denis Shapovalov (CAN x20) 7-6 (7/1), 6-3, 6-4
Radu Albot (MDA) bt Tennys Sandgren (USA) 7-6 (7/3), 7-6 (7/1), 3-6, 6-1
Lloyd Harris (RSA) bt Lukas Rosol (CZE) 6-1, 4-6, 2-6, 6-1, 6-2
Borna Coric (CRO x13) bt Aljaz Bedene (SLO) 6-1, 6-7 (4/7), 6-4, 6-4
Dominic Thiem (AUT x4) bt Tommy Paul (USA) 6-4, 4-6, 7-6 (7/5), 6-2
Alexander Bublik (KAZ) bt Rudolf Molleker (GER) 7-5, 6-7 (4/7), 6-1, 7-6 (7/2)
Pablo Cuevas (URU) bt Maxime Janvier (FRA) 6-4, 6-4, 6-2
Roberto Carballes Baena (ESP) bt Alexandre Muller (FRA) 6-4, 6-4, 6-2
Filip Krajinovic (SRB) bt Frances Tiafoe (USA x32) 6-2, 4-6, 6-3, 3-6, 6-0
Stan Wawrinka (SUI x24) bt Jozef Kovalik (SVK) 6-1, 6-7 (3/7), 6-2, 6-3
Cristian Garin (CHI) bt Reilly Opelka (USA) 7-6 (7/0), 7-5, 7-6 (9/7)
Jo-Wilfried Tsonga (FRA) bt Peter Gojowczyk (GER) 7-6 (7/4), 6-1, 4-6, 6-3
Alex De Minaur (AUS x21) bt Bradley Klahn (USA) 6-1, 6-4, 6-4
Pablo Carreno Busta (ESP) bt Joao Sousa (POR) 6-3, 6-1, 6-2
Benoit Paire (FRA) bt Marius Copil (ROU) 6-4, 6-7 (5/7), 6-0, 6-1
Pierre-Hugues Herbert (FRA) bt Daniil Medvedev (RUS x12) 4-6, 4-6, 6-3, 6-2, 7-5
Juan Ignacio Londero (ARG) bt Nikoloz Basilashvili (GEO x15) 6-4, 6-1, 6-3
Richard Gasquet (FRA) bt Mischa Zverev (GER) 6-3, 6-4, 6-3
Corentin Moutet (FRA) bt Alexey Vatutin (RUS) 6-4, 7-6 (8/6), 6-4
Guido Pella (ARG x19) bt Guido Andreozzi (ARG) 7-6 (7/2), 6-4, 1-6, 6-1
Miomir Kecmanovic (SRB) bt Denis Kudla (USA) 6-0, 6-7 (7/9), 5-7, 6-3, 6-4
Yannick Maden (GER) bt Kimmer Coppejans (BEL) 7-6 (7/0), 7-5, 6-3
Rafael Nadal (ESP x2) bt Yannick Hanfmann (GER) 6-2, 6-1, 6-3
Serena Williams (USA x10) bt Vitalia Diatchenko (RUS) 2-6, 6-1, 6-0
Sofia Kenin (USA) bt Giulia Gatto-Monticone (ITA) 6-3, 5-7, 6-2
Su-Wei Hsieh (TPE x25) bt Viktorija Golubic (SUI) 6-4, 3-6, 6-0
Andrea Petkovic (GER) bt Alison Riske (USA) 2-6, 6-3, 7-5
Danielle Collins (USA) bt Tatjana Maria (GER) 6-0, 6-2
Ashleigh Barty (AUS x8) bt Jessica Pegula (USA) 6-3, 6-3
Ekaterina Alexandrova (RUS) bt Mihaela Buzarnescu (ROU x30) 6-4, 6-4
Samantha Stosur (AUS) bt Barbora Strycova (CZE) 6-2, 7-6 (7/3)
Aliona Bolsova Zadoinov (ESP) bt Vera Zvonareva (RUS) 6-4, 6-2
Sorana Cirstea (ROU) bt Kaja Juvan (SLO) 5-7, 6-4, 7-5
Jennifer Brady (USA) bt Ivana Jorovic (SRB) 7-6 (7/5), 4-6, 7-5
Polona Hercog (SLO) bt Aliaksandra Sasnovich (BLR x32) 4-6, 6-2, 8-6
Rebecca Peterson (SWE) bt Yulia Putintseva (KAZ) 6-3, 7-5
Donna Vekic (CRO x23) bt Liudmila Samsonova (RUS) 6-2, 6-4
Johanna Konta (GBR x26) bt Antonia Lottner (GER) 6-4, 6-4
Lauren Davis (USA) bt Kristyna Pliskova (CZE) 6-2, 6-4
Viktoria Kuzmova (SVK) bt Alize Cornet (FRA) 6-4, 6-3
Kiki Bertens (NED x4) bt Pauline Parmentier (FRA) 6-3, 6-4
Shelby Rogers (USA) bt Astra Sharma (AUS) 6-3, 6-3
Carla Suarez Navarro (ESP x28) bt Dayana Yastremska (UKR) 2-6, 7-6 (7/0), 6-0
Elise Mertens (BEL x20) bt Tamara Zidansek (SLO) 6-4, 3-6, 6-2
Diane Parry (FRA) bt Vera Lapko (BLR) 6-2, 6-4
Mandy Minella (LUX) bt Anastasia Pavlyuchenkova (RUS) 6-4, 6-2
Anastasija Sevastova (LAT x12) bt Luksika Kumkhum (THA) 6-1, 6-4
Veronika Kudermetova (RUS) bt Caroline Wozniacki (DEN x13) 0-6, 6-3, 6-3
Zarina Diyas (KAZ) bt Audrey Albie (FRA) 6-2, 6-2
Zhang Shuai (CHN) bt Varvara Lepchenko (USA) 6-1, 6-1
Kaia Kanepi (EST) bt Julia Goerges (GER x18) 7-5, 6-1