The Isle of Skye, Scotland, has yielded a diverse Middle Jurassic terrestrial vertebrate fauna, but little is known about the predatory dinosaurs (theropods) occupying the top and secondary carnivore roles in these ecosystems, as their fossils have been limited to rare footprints of small- to mid-sized taxa. We describe two isolated theropod body fossils, a tooth and a middle-posterior caudal vertebra, from the late Bajocian–Bathonian Valtos Sandstone Formation of northeastern Skye, and use a variety of quantitative techniques to determine their taxonomic affinities. We conservatively refer both specimens to Theropoda indet., but suggest that the tooth most likely belonged to a megalosaurid, basal tyrannosauroid, or dromaeosaurid, and that the vertebra belonged to a small-bodied basal coelurosaur of approximately the same size as Coelurus (c. 2 m long, c. 30 kg mass). Although fragmentary, these fossils and the footprints demonstrate that both small and mid to large theropods were present in the Middle Jurassic of Scotland, and that these may have included some of the oldest coelurosaurs, and potentially some of the earliest-diverging tyrannosauroids and dromaeosaurids.