The single was initially announced on December 22, 2018 during Up Up Girls (2)’s First 7nin no Christmas event alongside an announcement of new member auditions for Up Up Girls (2). At this event, it was revealed that the new members would be debuting in a double A-side single produced by Tsunku on April 2, 2019. The title of the single and the results of the audition were announced on March 3, 2019, while the new members performed for the first time during a live performance at Mynavi BLITZ Akasaka on March 23, 2019.
On June 21, 2019, after the release of the single, Hashimura Riko announced her graduation from Up Up Girls (2) on July 29, alongside another announcement that their next single would be released in August. This makes "We are Winner / Starting Over" her last single with the group.
Making of We are Winner! アップアップガールズ（２）
スターティングオーバー アップアップガールズ（２） パフォーマンス
Starting Over (Performance)
「この指と〜まれ！ season3」presents We are Winner! MUSIC VIDEO Aya Kajishima EDIT.