To build a fashion recommendation system, we need to help users retrieve fashionable items that are visually similar to a particular query, for reasons ranging from searching alternatives (i.e., substitutes), to generating stylish outfits that are visually consistent, among other applications. In domains like clothing and accessories, such considerations are particularly paramount as the visual appearance of items is a critical feature that guides users' decisions. However, existing systems like Amazon and eBay still rely mainly on keyword search and recommending loosely consistent items (e.g. based on co-purchasing or browsing data), without an interface that makes use of visual information to serve the above needs. In this paper, we attempt to fill this gap by designing and implementing an image-based query system, called Fashionista, which provides a graphical interface to help users efficiently explore those items that are not only visually similar to a given query, but which are also fashionable, as determined by visually-aware recommendation approaches. Methodologically, Fashionista learns a low-dimensional visual space as well as the evolution of fashion trends from large corpora of binary feedback data such as purchase histories of Women's Clothing & Accessories from Amazon, which we use for this demonstration.