<p>Conventional computing is based on the concept of bits which are classical entities that are either 0 or 1 and can be represented by stable magnets. The field of quantum computing relies on qubits which are a complex linear combination of 0 and 1. Recently, the concept of probabilistic computing with probabilistic (<em>p-</em>)bits was introduced where <em>p-</em>bits are robust classical entities that fluctuate between 0 and 1. <em>P-</em>bits can be naturally represented by low-barrier nanomagnets. Probabilistic computers (<em>p-</em>computers) based on <em>p-</em>bits are domain-based hardware accelerators for Monte Carlo algorithms that can efficiently address probabilistic tasks like sampling, optimization and machine learning. </p> <p>In this dissertation, starting from the intrinsic physics of nanomagnets, we show that a compact hardware implementation of a <em>p-</em>bit based on stochastic magnetic tunnel junctions (s-MTJs) can operate at high-speeds in the order of nanoseconds, a prediction that has recently received experimental support.</p> <p>We then move to the system level and illustrate by simulation and by experiment how multiple interconnected <em>p-</em>bits can be utilized to train a Boltzmann machine built with hardware <em>p-</em>bits. We observe that even non-ideal s-MTJs can be utilized for probabilistic computing when combined with hardware-aware learning.</p> <p>Finally, we show how to build a <em>p-</em>computer to accelerate a wide variety of problems ranging from optimization and sampling to quantum computing and machine learning. The common theme for all these applications is the underlying Monte Carlo and Markov chain Monte Carlo algorithms and their parallelism enabled by a unique <em>p-</em>computer architecture.</p>