Novel computational paradigms may provide the blueprint to help solving the time and energy limitations that we face with our modern computers, and provide solutions to complex problems more efficiently (with reduced time, power consumption and/or less device footprint) than is currently possible with standard approaches. Spintronics offers a promising basis for the development of efficient devices and unconventional operations for at least three main reasons: (i) the low-power requirements of spin-based devices, i.e., requiring no standby power for operation and the possibility to write information with small dynamic energy dissipation, (ii) the strong nonlinearity, time nonlocality, and/or stochasticity that spintronic devices can exhibit, and (iii) their compatibility with CMOS logic manufacturing processes. At the same time, the high endurance and speed of spintronic devices means that they can be rewritten or reconfigured frequently over the lifetime of a circuit, a feature that is essential in many emerging computing concepts. In this perspective, we will discuss how spintronics may aid in the realization of efficient devices, primarily focusing on magnetic tunnel junctions. We then provide a perspective on how these devices can impact the development of three unconventional computing paradigms, namely, reservoir computing, probabilistic computing and memcomputing. These paradigms may be used to address some limitations of modern computers, providing a realistic path to intelligent hybrid CMOS-spintronic systems.