Sahasralah sends Link to the Eastern Palace to find his pupil, Osfala. Link finds, however, that he cannot proceed without the Bow, and discovers a note directing him to Ravio's shop (formerly Link's House). Upon visiting Ravio, Link rents the Bow, and proceeds to the Eastern Palace. When he reaches the entrance, he finds Osfala, who has rented the Sand Rod from Ravio; however, Link is unable to stop Osfala from entering the Palace. Link traverses the dungeon, at the end of which he finds Yuga and Osfala. Yuga transforms Osfala into a Portrait and does battle with Link. The confrontation ends with Yuga transforming Link into a Portrait and Yuga escaping; however, Link finds that Ravio's Bracelet allows him to escape the painting and reenter walls as a painting at will.
The puzzles in the Eastern Palace revolve around the Bow, which Link must obtain from Ravio in order to reach the dungeon. Although a shield isn't necessary, it is very helpful due to the many arrow traps within.
As part of the A Link Between Worlds DLC, the Eastern Palace appears on the Hyrule portion of the Lorule Adventure Map.