Shoujo anime is famous for its big eyes and magical transforming heroines.
Sailor Moon is probably the most famous of these.
When was the first time a magical girl magically transformed?
The first 'magical girl' anime was Sally The Witch, who transformed with a wand into another costume - This was a simple animation though and performed in the same cut as the rest of the scene. Sally The Witch came out in 1966 and was in black and white.
[Apologies for low-quality gif]
If however, that feels like a bit of a cop out answer, the anime Cutey Honey which was released in 1973 was much more focused on the transformation scene and featured many of the tropes of this type of this scene which have lasted to this very day - magical jewelery, activation words ("HONEY FLASH"), nudity whilst transforming, floating around the screen while transforming, etc.
Surprisingly though, Cutey Honey was not a shoujo, it was a male-targetted show and the characters were thought at the time to be superheroes rather than magical girls. However, Cutey Honey was a significant influence on transformation scenes from then on and looking back at the show, it's surprising to think that they are not actually magical girls. They even have the catchphrase "Stars in the heavens! Flowers on the Earth! Love to the people! Warrior of Love, I am Cutey Honey!"
(partial sequence sped up)
Cutie Honey is a much bigger deal in Japan than it is in the US. This is primarily due to it not being available in North America and other English-speaking countries until Discotek released it in 2013.
As it was back in the day, there weren't such a high volume of series airing at one time. Inbetween Sally the Witch and Cutey Honey, there was only one other magical girl anime - Himitsu no Akko-chan, who transformed similarly to Sally the Witch, albeit with a mirror instead of a wand.
And if you're interested in transforming robots too, check out this question.
Toei does consider Cutie Honey a magical girl although it was a shounen series and although her transforming powers aren't technically "magical." Despite being a shonen series Honey's influence on later, more traditional magical girls was immediate, as it was followed by Majokko Megu-chan in 1974 which was sort of an amalgam of the traditional Sally/Chappy "witch comes to earth" storyline and the ecchi humor of Honey.
There were several other magical girl series between Akko-chan and Cutie Honey, by the way. Toei (which also produced Sally and Akko) made another four between 1970-73 (Mahou no Mako-chan, Sarutobi Ecchan, Mahou Tsukai Chappy, and Miracle Shoujo Limit-chan, which was on the air contemporaneously with Cutie Honey but premiered a few days earlier). Although Chappy was the only "witch" among those four (Ecchan's only magical power is the ability to jump high, Mako-chan had a magical pendant a la Akko, and Limit-chan was, like Honey, a cyborg), all of them are classified as magical girls by Toei. Many also consider Osamu Tezuka's Marvelous Melmo a magical girl series. Melmo and Limit also had transforming abilities - Melmo transformed into older and younger versions of herself by eating candy, and Limit had a sort of magical compass which in addition to allowing her to transform by saying "Change face!" gave her "miracle powers" such as the ability to run fast.
As for the first magical girl series to include "stock" henshin sequences a la Sailor Moon, I believe that was Mahou no Princess Minky Momo in 1982 (also a nude henshin, although only seem from behind). I don't think Honey included any stock transformations.