The objective of this study was to develop a new optimal parallel algorithm for matrix multiplication which could run on a Fibonacci Hypercube structure. Most of the popular algorithms for parallel matrix multiplication can not run on Fibonacci Hypercube structure, therefore giving a method that can be run on all structures especially Fibonacci Hypercube structure is necessary for parallel matrix multiplication. For creating this method, a new model for matrix multiplication with an algorithm for data distribution on Fibonacci Hypercube structure was provided. Other than this, another optimized algorithm was designed on Mesh structure. By running the algorithms on a simulative parallel system and giving the results in graphical mode, it has been found that these two algorithms have optimized value in parallel matrix multiplication and they are more efficient than the previous algorithms.