Utilizing complex-valued neural networks (CVNNs) in wireless communication tasks has received growing attention for their ability to provide natural and effective representation of complex-valued signals and data. However, existing studies typically employ complex-valued versions of simple neural network architectures. Not only they merely scratch the surface of the extensive range of modern deep learning techniques, theoretical understanding of the superior performance of CVNNs is missing. To this end, this paper aims to fill both the theoretical and practice gap of employing CVNNs in wireless communications. In particular, we provide a comprehensive description on the various operations in CVNNs and theoretically prove that when the output dimension is large, the CVNN requires fewer layers than its real-valued counterpart to achieve a given approximation error of a continuous complex-valued function. Furthermore, to advance CVNNs in the field of wireless communications, this paper focuses on the transformer model, which represents a more sophisticated deep learning architecture and has been shown to have excellent performance in wireless communications but only in its real-valued form. In this aspect, we propose a fundamental paradigm of complex-valued transformers for wireless communications, including the complex-valued embedding module, encoding module, decoding module, and output projection module. Leveraging this structure, we develop customized complex-valued transformers for three representative applications in wireless communications: channel estimation, user activity detection, and joint design of pilot, feedback quantization, and precoder. These applications utilize transformers with varying levels of sophistication and span a variety of tasks, ranging from regression to classification, supervised to unsupervised learning, and specific module design to end-to-end design. Experimental results verify the theoretical advantage and effectiveness of the complex-valued transformers for the above three applications compared to other traditional real-valued neural network-based methods.