After a disappointing inaugural season drastic changes were made to the playing staff including the retirement of experienced campaigners Sharon Black and Dianne Alagich to create a youthful team for the 2009 season. Despite the new look squad Adelaide continued to struggle in the league failing to win any of the first 5 games which included a record equaling defeat against Sydney FC on 1 November 2009. The first goal of the 2009 season was scored by Tenneille Boaler against Newcastle Jets in the round 6 clash at the Wanderers Oval the game ended in a 3 – 3 draw handing Adelaide its second point of the year. The season didn't get any better for Adelaide as they failed to win a single game in the second season but thanks to an unlikely 2 all draw with power house team Brisbane Roar they finished the season in 7th place their best ever finish to date. Most Valuable player for 2009 season Racheal Quigley.
The 2010-11 season was even worse for the Lady Reds as they lost all ten of their W-League matches. They only scored four goals and finished with a disappointing -32 goal differential; they tied their worst defeat with a 7-1 loss to Newcastle in round nine. Coach Michael Barnett was let go at the end of the disappointing season, and was replaced by David Edmondson.
Adelaide continued to struggle through most of the 2011-12 season as they opened the campaign with six more losses, scoring four goals during that time while letting twenty-one in. This was better pace than the previous season, though, and the Lady Reds showed significant improvement in on-field play versus 2010-2011, cited as being "unlucky" to not come away with at least a point on multiple occasions. The finally snapped their winless and losing streaks, at 34 and 18 games respectively, with a 1-0 defeat of the Perth Glory in round eight, taking them off the bottom of the table for the first time since November 2009.
Since its inception Adelaide United has played in a predominantly all-red home kit. For the inaugural season the away kit consisted of a white top and socks and red shorts; during the 2009 season the away kit changed to a black top with red shorts and socks.
The badge is heavily based on the Adelaide United men's team, with the logo being encased in a W-League shield; as is the case with every other W-League club.