The majority of the work on underwater communication has mainly been based on acoustic communication. Acoustic communication faces many known problems, such as high propagation delays, very low data rates, and highly environment-dependent channel behavior. In this article, to address these shortcomings, magnetic induction is introduced as a possible communication paradigm for underwater applications. Accordingly, all research challenges in this regard are explained. Fundamentally different from the conventional underwater communication paradigm, which relies on EM, acoustic, or optical waves, the underwater MI communications rely on the time varying magnetic field to covey information between the transmitting and receiving parties. MI-based underwater communications exhibit several unique and promising features such as negligible signal propagation delay, predictable and constant channel behavior, sufficiently long communication range with high bandwidth, as well as silent and stealth underwater operations. To fully utilize the promising features of underwater MI-based communications, this article introduces the fundamentals of underwater MI communications, including the MI channel models, MI networking protocols design, and MI-based underwater localization.