As the rapid pace of Moore's Law has been slowing down, there has been intense activity to “reinvent the transistor.” An emerging paradigm is to complement the existing complementary metal-oxide-semiconductor (CMOS) technology with new functionalities, rather than finding a drop-in replacement for it. In this article, we discuss such a complementary approach that we call probabilistic spin logic (PSL) based on the concept of a probabilistic or p-bit. p-bits fluctuate between 0 and 1 and can be imagined in between deterministic bits that are either 0 or 1 and quantum bits that are a superposition of 0 and 1. Interconnected circuits built out of p-bits (p-circuits) can be broadly useful for machine learning and quantum computing in the solution of problems that conventional CMOS may not be particularly suited for. Although such p-bits can be implemented using standard CMOS technology, we will show that the inherent physics of nanomagnets can naturally provide an energy efficient and scalable p-bit implementation through the use of low-barrier magnetic tunnel junctions (MTJs). In this article, we provide a general description of p-bits and p-circuits and discuss their applications. We review experimental progress toward constructing p-bits and p-circuits exploiting the inherent stochasticity of nanomagnets, from a physics/device/circuits perspective. In particular, we identify building blocks for “write” and “read” operations that can be used in different combinations to construct functional p-bits and p-circuits. Finally, we discuss the prospects and challenges of PSL as an emerging, unconventional computing paradigm for a beyond CMOS era.