Substitution box (S-box) plays an important role in block cipher to protect data from any threats. The need for secure cipher is ever-increasing to protect data in several ways to provide confidentiality, integrity and authentication. The data is encrypted to prevent unauthorized users from accessing the information. However, as stated in the National Strategy ICT Roadmap, security is one of the pressing needs and critical infrastructure in Malaysia. In addition, within the advancement of technology the design of cryptographic algorithm in block cipher is often enhanced to ensure that the information is secure. Therefore, this paper proposed the new S-box using the concept of Fibonacci number in nature to improve the security of block cipher algorithm. Result showed that the new proposed S-box using the Fibonacci number possessed good cryptographic properties.