The operational matrices-based computational algorithms are the promising tools to tackle the problems of non-integer derivatives and gained a substantial devotion among the scientific community. Here, an accurate and efficient computational scheme based on another new type of polynomial with the help of collocation method (CM) is presented for different nonlinear multi-order fractional differentials (NMOFDEs) and Bagley-Torvik (BT) equations. The methods are proposed utilizing some new operational matrices of derivatives using Chelyshkov polynomials (CPs) through Caputo's sense. Two different ways are adopted to construct the approximated (AOM) and exact (EOM) operational matrices of derivatives for integer and non-integer orders and used to propose an algorithm. The understudy problems have been transformed to an equivalent nonlinear algebraic equations system and solved by means of collocation method. The proposed computational method is authenticated through convergence and error-bound analysis. The exactness and effectiveness of said method are shown on some fractional order physical problems. The attained outcomes are endorsing that the recommended method is really accurate, reliable and efficient and could be used as suitable tool to attain the solutions for a variety of the non-integer order differential equations arising in applied sciences. © 2020 by the authors.