The music video was directed by Melina. It was released on October 29, 2009.
The video pays homage to several scenes in The Princess and the Frog. It takes place in New Orleans in possibly the jazz age—the time period the film is set. It starts with Ne-Yo walking through the empty streets fantasizing about a woman as jazz musicians play behind him. He walks into a restaurant where he works as a waiter the woman / "Princess" character is a beautiful and clearly wealthy customer who is dining with her family. Ne-Yo then goes into an empty warehouse which he imagines is a kitchen (homage to the scene in which Almost There is performed). He dreams the woman has come to visit him and they are eating some of Ne-Yo's cooking and having a good time with each other. Ne-Yo then takes a streetcar and he sees the woman with her family outside the home through the window. The woman looks up and sees him on the streetcar and runs after it. This is intercut with Ne-Yo overlooking the bayou where a large portion of the Princess and the Frog takes place. He turns around and the woman is standing behind him the two run to each other and share a kiss while two frogs on the bayou are also seen kissing.