Practical tools to quantify range-wide dietary choices of the polar bear have not been well developed, thus impeding the monitoring of this species in a changing climate. Here we describe our steps toward non-invasive polar bear diet determination with the optimization of 454 pyrosequencing of a 136 base pair (bp) mitochondrial cytochrome b (cytb) fragment amplified from the extracts of captive and wild polar bear faeces. We first determine the efficacy, reliability, and accuracy of our method using five faecal samples from a captive polar bear fed a known diet at the Canadian Polar Bear Habitat in Cochrane, Ontario, Canada; 19 samples from three polar bears at the Metro Toronto Zoo, Toronto, Ontario, Canada; and seven samples from seven wild (unfed) polar bears from a holding facility in Churchill, Manitoba, Canada. We report 91% overall success in amplifying a 136 bp cytb amplicon from the faeces of polar bears. Our DNA analyses accurately recovered the vertebrate diet profiles of captive bears fed known diets. We then characterized multiyear vertebrate prey diet choices from free-ranging polar bears from the sea ice of the M'Clintock Channel polar bear management unit, Nunavut, Canada (n = 117 from an unknown number of bears). These data point to a diet unsurprisingly dominated by ringed seal (Pusa hispida) while including evidence of bearded seal (Erignathus barbatus), harbour seal (Phoca vitulina), muskox (Ovibos moschatus ssp.), Arctic fox (Vulpes lagopus), wolf (Canis lupus), Herring Gull (Larus argentatus), and Willow Ptarmigan (Lagopus lagopus). We found low levels of contamination (< 3% of sequences when present) and suggest specific process improvements to reduce contamination in range-wide studies. Together, these findings indicate that next-generation sequencing-based diet assessments show great promise in monitoring free-ranging polar bears in this time of climate change.