Wesley was born and raised in Las Vegas, Nevada. Wesley's father, Ivery Wheeler, is a professional tap dancer and her mother, Cassandra Wesley, was a showgirl. She attended high school at the Las Vegas Academy of International Studies, Performing and Visual Arts. She studied dance at Simba Studios and the West Las Vegas Arts Center.
While at the Las Vegas Academy, Wesley missed several other auditions for college training programs and was finally accepted by the University of Evansville in Indiana. She was hesitant in joining the university because of a lack of minorities in the state. After earning her undergraduate degree in Theatre Performance (B.F.A. 2001), her grandmother suggested that she do a nursing course, but Wesley insisted on pursuing her education. She joined the Juilliard School in 2001 and graduated in May 2005 (Group 34), which included a summer spent at the Royal Academy of Dramatic Art. At Juilliard, she became close friends with her future co-star Nelsan Ellis (Group 33: 2000–2004).
Wesley had a minor role in 2005 film Hitch, which was edited in the final cut. However, she made her on screen debut in the lead role in 2007 film How She Move, from British director Ian Iqbal Rashid. The character Raya Green, who enters a step dancing competition to secure funds for her education, was inspired by Tony Manero, portrayed by John Travolta in Saturday Night Fever. Prior to the shooting of the film, Wesley underwent a five-week dance rehearsal period. Portraying a woman of Jamaican descent, she also took dialect coaching for the role. Wesley auditioned for the role Tara Thornton in the HBO series True Blood in 2007 and secured the part after creator Alan Ball chose her because "[she] was the first person who showed [Tara's] vulnerable side".
Wesley divides her time between Los Angeles and Astoria, Queens. In 2005 she married her former Juilliard classmate Jacob Fishel, an actor. Rutina filed for divorce on August 16, 2013 citing irreconcilable differences.