In this paper we introduce and study k-order Gaussian Fibonacci Coding Theory. We give illustrative examples about coding theory. This coding theory is a method bound to the Q_k, R_k and E_n^(k) matrices. This coding/decoding method is different from classical algebraic coding. k-order Gaussian Fibonacci Coding method depends on matrix multiplication and can be performed quickly and easily by today’s computers. This method will not only ensures information security in data transfer but also has high correct ability. Consequently, this method aims to increase the reliability of information transfer by moving the coding theory to the complex space.