We present the results of experimental and theoretical study of the structural and electronic properties of the (0 0 1) surface of an ordered, paramagnetic Ni3Al alloy. Experimental part of this work is based on STM measurements which enabled us to obtain, for the first time, images of the Ni3Al(0 0 1) surface with atomic resolution. Topographies of these images indicate the presence of a superstructure with the square unit cell and the lattice parameter equal to the distance between nearest surface Al or Ni atoms. We have observed that this order of the Ni3Al(0 0 1) surface has a long-range character. This is remarkably different from the Ni3Al(1 1 1) surface, where a (2 × 2) order (indicated by previous STM study) appears only within small surface domains. Our theoretical study of Ni3Al(0 0 1) is based on ab initio calculations performed in the framework of density-functional theory and the use of a plane wave basis set. The obtained results indicate that changes of the atomic positions caused by the relaxation process are small and practically limited to the three topmost atomic layers. However, in the relaxed structure, surface Al atoms have higher vertical positions than surface Ni atoms, in accordance with experimental data provided by LEED measurements. We have also analyzed the differences between results of structural calculations performed independently using LDA and GGA descriptions of the exchange-correlation effects, and found that the GGA results are in a considerably better agreement with LEED data than the corresponding LDA results or the results of earlier theoretical studies.